关于图、树和遍历顺序可以先看我的这篇文章<<图，树，图的遍历顺序（Graphs，Trees and Traversal Oreder of Graphs>>

支配节点（dominator）

流图中，每一条从入口节点到节点n的路径都经过节点d，则d支配（dominate）n，记d dom n。按照这个定义，每个节点都支配自己。—龙书

上图中，节点1支配流图中所有节点，节点2只支配它自己，节点3支配除节点1和节点2以外所有节点。

严格支配节点（strictly dominator）

在上述支配节点中，若d != n 且d dom n，则d严格支配n，记d sdom n。

上述流图中，1 sdom 2，1 sdom 3。

支配节点树（dominator tree）

使用支配节点树来表示流图的支配信息。在数中，入口节点就是根节点，并且每个节点d只支配它在树中的后代节点。

前面流图的的支配节点树如下图。

直接支配节点（immediate dominator）

在支配节点树上，从根节点到节点n的路径上，离节点n最近的节点是节点n的直接支配节点。

比如，4 idom 5。

支配节点性质

• 自反性：每个节点都是自己的支配节点。
• 传递性：a dom b，b dom c，则a dom c。
• 反对称：a dom b，b dom a，则a = b。

支配节点树构建算法

以下求解支配节点树的主要算法参考Henrik Knakkegaard Christensen的论文Algorithms for Finding Dominators in Directed Graphs 和 再谈Dominator Tree的计算。

节点删除法（Vertex-removal Algorithms）

一种比较naive的构建支配节点树的方法，在DG上，从根节点以DFS方式去检查是否每个节点都可以从根节点到达。对于每个节点w，把它从DG上去除，然后从根节点做DFS，若之前能访问到但现在访问不到的这些节点，则受节点w支配。对每个节点，我们使用上述方法，则每个节点我们都可以得到受它支配的节点列表，也就是说在支配节点树上，列表中的所有节点都是该节点的子树，这样我们便很轻松构建支配节点树。

直接上Henrik Knakkegaard Christensen论文中的图。

节点删除法是根据支配节点的定义来做的，非常简单，显然算法的复杂度也很高O(n*m)。

迭代数据流（Iteraval Algorithms）

论文中介绍了两种迭代算法，它们的复杂度都是O(m*n^2)，通过对一个给定graph初始化一个错误的dominators解，然后迭代处理每个节点来改变这个解，使它逐渐接近正确的dominators解，直到得到正确的dominators解。

Data-Flow Equation, Boolean Vector Algorithm

Allen在1970年定义了计算dominators的数据流方程，对于节点v，它的支配节点是它自己并上它所有前驱的支配节点的交集，如下：

显然，对于一个DG，根据以上数据流方程，需要迭代进行求解。使用boolean vector表示节点v的dominators集合，对于每个节点v的boolean vector，节点w若支配节点v，则w在vector中为true，否则为false。算法如下：

通过下面的例子来介绍如何使用boolean vector来迭代求解dominators关系。

这个例子中，没有使用优化的顺序遍历，节点的编号就是遍历的顺序。每次迭代，dominator boolean vector变化了，对应节点会标记成蓝色。图a，第0轮迭代，将根节点r支配节点初始化为{r}，其他节点的支配节点初始化为V（所有节点）。图b，第一轮迭代，节点1和3不会继承它们前驱的任何变化，节点2和4继承节点r的变化，节点5会继承2和4的变化。图c，第二轮迭代，节点1继承节点2的变化，节点3继承节点4的变化。图d，第三轮迭代，节点1集成节点3的变化。图e，最后一轮迭代，每个节点的dominator boolean vectotr都不会发生变化，迭代结束。

复杂度：每轮迭代，每个节点需要计算它所有前驱的交集，在graph中共有m个前驱，则会有m次交集计算。dominator boolean vector的size是n，则每轮迭代计算所有节点交集的总时间为O(mn)。算法最多迭代n-1次，因此总的迭代时间是O(mn^2)。空间复杂度显然为O(n^2)。

Dominator-tree Algorithm

另一种数据流迭代算法是将DG的有向生成树（Directed spanning tree）转化为dominator tree，这种算法较上一节介绍的算法，复杂度更低。该算法基于以下两个观察结果：

一、在Dominator tree中，每个节点的直接支配节点（immediate dominator）是它的父亲（parent）。

二、DG中每个节点的immediate dominator在其Directed spanning tree都是它的祖先（ancesstor）。因为DG中任一达到一个节点的路径都经过它的支配节点。

算法的迭代过程就是把有向生成树转换为支配节点树的过程，如下图，其中NCA表示nearest-common-ancestor。

下面给出一个例子来说明算法的处理过程。

图a是输入的graph。图b是图a的一个subgraph，也是graph的有向生成树，其中虚线边代表是原图的边，但在有向生成树中不存在，实线边代表有向生成树上的边。图c，第一次迭代，节点1满足算法中第5行的方程。类似地，图d中节点5满足方程。图e没有节点满足方程了，算法迭代结束，得到dominator tree。

复杂度：有向生成树计算时间为O(m)，NCA使用naively的方法计算需要时间为O(n)，每轮迭代计消耗O(m) 时间计算NCA，因此总的时间复杂度为O(mn^2)。空间消耗为O(m+n)。

Semidominators

下面介绍的两种方法都借助一个叫做半支配节点（semidominators）的概念，半支配节点是对直接支配节点的一种逼近，这里先介绍半支配节点的概念和求解方法。

先使用DFS方法得到有向图的preorder排序和DFST，然后定义半支配节点如下（注意：这里对半支配节点的标记和上文中提到的严格支配节点一样，注意区分）：

这里直接贴一个再谈Dominator Tree的计算中的图片。

该例子，使用DFS得到的preorder排序和DFST（红色边），对于节点15，可以找到半支配节点路径包括：

• 14-15
• 11-15
• 3-18-19-15
• 2-21-22-23-16-27-15

因此$sdom(15)=2$。

有半支配节点得到几个引理，这里直接贴下《Algorithms for Finding Dominators in Directed》中引理和解释：

后面的LT算法将由这些引理推出。

这里介绍半支配节点的算法。

方法一：根据上面的半支配节点的定义，观察节点v的半支配节点路径。观察v的前驱，若前驱节点p的编号小于v，则是候选半支配节点。若前驱节点p的编号大于节点v，则继续找p的前驱，直到找到最小编号的顶点作为候选节点。比较上述候选节点，最小编号的节点即为半支配节点。该方法有比较多的重复计算。

方法二：一种更快计算所有顶点的半支配节点的方法，是以逆前序（reverse preorder）方式计算半支配节点，这样当计算v的半支配节点时，所有$v^{{}^{\prime }}$的半支配节点已经计算过了。

第一步：对于序号小于v的前驱节点可以很简单找到。例如节点15，满足条件的是节点11和14，并且11最小。

第二步：对于前驱序号大于节点v的节点q，通过求节点q的半支配节点来求解v的半支配节点，递归求解直到找到序号小于v的节点。由于是逆前序遍历，序号大的节点的半支配节点已经求解过了。对于前驱节点19，$sdom(sdom(19))=3$，对于前驱节点17，$sdom(sdom(17))=2$。

第三步，取第一二步骤中最小节点，即2。

Lengauer-Tarjan

由半支配节点得到的几个引理，可以得到LT的算法：

LT算法和思想就是通过半支配节点来逼近直接支配节点，先求半支配节点，然后根据不同情况求取直接支配节点。

SEMI-NCA

SEMI-NCA算法是semidominator和NCA (nearest common ancestor)的组合。以前序顺序遍历DFST，创建dominator tree。

SEMI-NCA算法如下：

一个例子：

参考

• [1] 龙书
• [2] https://blog.csdn.net/dashuniuniu/article/details/52224882
• [3] Algorithms for Finding Dominators in Directed Graphs（http://www.cs.au.dk/~gerth/advising/thesis/henrik-knakkegaard-christensen.pdf）
• [4] https://blog.csdn.net/dashuniuniu/article/details/103462147?spm=1001.2014.3001.5501