支配树与 Lengauer–Tarjan 算法

支配关系与问题范围 ​

设有向 flow graph $G=(V,E)$ 有指定入口 $r$，本页只处理从 $r$ 可达的顶点。若每条从 $r$ 到 $v$ 的有向路径都经过 $u$，称 $u$ 支配 $v$，记 $u\mathrm{dom}v$。每个顶点支配自身，$r$ 支配全部可达顶点。

对 $v\ne r$，所有严格支配 $v$ 的顶点按支配关系形成一条链；最靠近 $v$ 的那个称为立即支配点 $\mathrm{idom}(v)$。边

$$(\mathrm{idom}(v),v),v\ne r$$

形成 dominator tree，而且

$$u\mathrm{dom}v⟺u\text{是 dominator tree 中 }v\text{ 的祖先}.$$

算法输出所有 $\mathrm{idom}(v)$。令 $n$、$m$ 分别为可达子图的顶点与边数；简化 eval/link 实现为 $O(m\log n)$，Lengauer–Tarjan 的路径压缩版本为

$$O(m\alpha (m,n))$$

时间、$O(n+m)$ 空间。这里的并查集维护 DFS 祖先路径上的标签最小值，不是普通无向连通分量 DSU。

DFS 树不是支配树 ​

先从 $r$ 做 DFS公理库深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。，按发现顺序给顶点编号

$$1=\mathrm{dfn}(r)<\mathrm{dfn}(v)\le n$$

并记录 DFS parent。DFS parent 只说明搜索第一次怎样到达 $v$；另一条非树边可能绕开它，因此通常不支配 $v$。

定义 $v\ne r$ 的 semidominator $\mathrm{sdom}(v)$ 为 DFS 编号最小的顶点 $u$，使存在路径

$$u=w_0,w_1,\dots ,w_k=v$$

且所有内部顶点 $w_1,\dots ,w_{k-1}$ 的 DFS 编号都严格大于 $\mathrm{dfn}(v)$。直接树边保证集合非空。Semidominator 描述“在不提前进入已处理 DFS 前缀的前提下，最早能从哪里跳到 $v$”，它不必支配 $v$，更不等于 $\mathrm{idom}(v)$。

反向 DFS 扫描与 eval/link ​

算法按 DFS 编号从 $n$ 递减到 $2$ 处理顶点 $w$。对每条进入 $w$ 的边 $(v,w)$：

• 若 $\mathrm{dfn}(v)<\mathrm{dfn}(w)$，$v$ 本身可作 semidominator 候选；
• 否则候选是 $\mathrm{sdom}(\mathrm{eval}(v))$。

$\mathrm{link}(p,w)$ 把已处理顶点 $w$ 接到 DFS parent $p$ 的 ancestor forest 中。$\mathrm{eval}(v)$ 返回从 $v$ 沿当前 ancestor 路径到根、具有最小 semidominator 编号的代表标签。带压缩的 eval 在缩短路径时还维护这项最小标签；若只调用普通 find 返回集合根，会丢掉算法真正需要的信息。

扫描所有 predecessors 后，得到

$$\mathrm{sdom}(w)=\underset{\text{按 DFS 编号}}{min}\{\mathrm{sdom}(\mathrm{eval}(v)):(v,w)\in E\},$$

其中祖先 predecessor 按其自身编号解释。把 $w$ 放进 bucket$[\mathrm{sdom}(w)]$，再 link$(\mathrm{parent}(w),w)$。

bucket 延迟决定 idom ​

当处理完 $w$ 并把它 link 到父亲后，取出 bucket$[\mathrm{parent}(w)]$ 中的每个顶点 $v$。令 $u=\mathrm{eval}(v)$：

$${\mathrm{idom}}^{\prime }(v)=\{\begin{array}{ll}u,& \mathrm{dfn}(\mathrm{sdom}(u))<\mathrm{dfn}(\mathrm{sdom}(v)),\\ \mathrm{parent}(w),& \text{否则}.\end{array}$$

这是 provisional dominator。桶机制等到 $\mathrm{sdom}(v)$ 所在 DFS 子树的必要祖先信息已经进入 eval/link，再决定它；过早处理会漏掉经后向边到达的更小候选。

最后按 DFS 编号从 $2$ 到 $n$ 做修正：

$$\mathrm{idom}(v)=\{\begin{array}{ll}\mathrm{sdom}(v),& {\mathrm{idom}}^{\prime }(v)=\mathrm{sdom}(v),\\ \mathrm{idom}({\mathrm{idom}}^{\prime }(v)),& \text{否则}.\end{array}$$

第一遍从路径结构找出 semidominator 和一个位于正确支配链上的代表，第二遍沿已经确定的 idom 把代表提升到真正立即支配点。

正确性的关键桥 ​

Semidominator lemma 说明：任意到达 $v$ 的路径，要么在进入 $v$ 前经过 $\mathrm{sdom}(v)$，要么含一个顶点 $u$，其 semidominator 编号比 $v$ 的更小；eval 正是在 DFS 祖先链中找出这类最小标签。若 provisional 候选没有更小 semidominator，$\mathrm{sdom}(v)$ 已是所有入口路径不可绕过的最近公共门；否则真正 idom 与 provisional 候选共享同一个 idom，第二遍递归修正。

DFS 逆序保证 eval 查询涉及的较深顶点都已 link，桶又保证候选只在所需 semidominator 阶段结算。每条图边只参与一次 predecessor 扫描；总复杂度因而由 $m$ 次 eval/link 的并查集代价主导。

具体例子：菱形控制流 ​

考虑

$$r\to a,r\to b,a\to c,b\to c,c\to d.$$

若 DFS 先走 $r,a,c,d$，则 $a$ 是 $c$ 的 DFS parent；但路径 $r\to b\to c$ 绕过 $a$，所以 $a$ 不支配 $c$。所有到 $c$ 的路径只共同经过 $r$，故

$$\mathrm{idom}(a)=r,\mathrm{idom}(b)=r,\mathrm{idom}(c)=r,\mathrm{idom}(d)=c.$$

支配树与这棵 DFS 树不同，正说明“某条搜索路径经过”不能替代“所有入口路径经过”的量词。

失败边界与相邻概念 ​

从 $r$ 不可达的顶点没有本页入口语义下的支配关系，应先排除或放入独立区域，不能给它们随意指定 idom。Postdominator 要在反向控制流图上从统一出口计算；多出口程序通常加虚拟出口，不能只把箭头翻转而保留原入口。

Low-link公理库Low-link 值Low-link value · LowlinkDFS 子树通过树边和受允许的返祖边能够到达的最早发现时间摘要。研究无向 DFS 子树能否经回边到达祖先，semidominator 研究有向 flow graph 中受 DFS 编号约束的路径；公式外观相似但对象完全不同。若只需迭代数据流方程，Cooper–Harvey–Kennedy 算法更易实现，在实际 CFG 上可能很快，但其最坏理论界与 Lengauer–Tarjan 路线不同。

参考资料

• Thomas Lengauer and Robert E. Tarjan, “A Fast Algorithm for Finding Dominators in a Flowgraph,” ACM Transactions on Programming Languages and Systems 1(1), 1979, 121–141.
• Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy, “A Simple, Fast Dominance Algorithm,” Rice University technical report, 2001.
• Robert E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983.