什么是统治者节点和统治者树？

Question

我尝试阅读wikipedia关于 Dominator（图论）给出以下定义Dominator节点：

节点D如果从条目节点到n的每条路径都将节点n主导 必须经过D.

我需要了解统治者节点的概念，但我不需要深入图形，所以我试图了解这些定义。我正在尝试在文章上查看图像：

这是一个图：

这应该是上图的图形的统治者树：

基于上面的定义，我认为

节点2主导节点3，因为3的每条路径必须通过2.为什么？从3到自己，我必须传递到2.这就是为什么2在统治者树中去3。

我在想对吗？

我也可以知道为什么这在编译器中有用吗？

Answer 1

你给出的原因并不是正确的;主导节点的定义从一个起始节点（ $ 1 $ 中的起始节点）工作。 aft $ 3 $ 从 $ 1 $ 是to to to to to to to to to class=“math-container “> 2美元$ ，因为它是给定图中 $ 1 $ 的唯一继承节点。因此 $ 2 $ 主导 $ 3 $ 。出于同样的原因，节点 $ 4 $ 通过 $ 6 $ 也是由 $ 2 $ 以及 $ 2 $ 是这些节点的主导者的立即（如 $ 1 $ 主导 $ 2 $ ），这些节点也不由任何其他节点主导而不是 $ 1 $ 和 $ 2 $ ：

• $ 3,4 $ 和 $ 6 $ 可以立即从 $ 1 $ 通过 $ 2 $ 。
• $ 5 $ 可以从 $ 2 $ 通过 $ 3 $ 或 $ 4 $ ，因此这些路径中唯一的常见节点到 $ 5 $ $ 1 $ 和 $ 2 $ 。

用于将这些概念应用于编译器，考虑程序的块级控制流程图（或简洁的CFG）。 如果某些块 $ b $ 占主导地位的块 $ b'$ 在cfg中，则 $ B $ 必须在程序到达 $ b'$ 时执行。 此知识可用于删除冗余代码： 考虑程序

a = (something)
b = True

if a == True:
   b = True
else:
   b = False
   

.

这里，由前两行组成的块主导IF-块以及else-块。 因此，我们知道，随着我们将b的if-block跳转到true，它已经被拳头块设置为true，因此编译器可以通过删除if-block中的赋值来优化代码。

您还可以通过分析CFG具有 $ b'\ to b $ 的边缘，从而通过分析来检测代码中的循环，其中 $ B $ 占主导地位 $ B'$ 。这样的路径表示存在一个循环，其中 $ b $ 然后表示循环标题，而 $ b'$ 是循环体的（最后）部分。