支配树与 Lengauer–Tarjan 算法

DFS 编号提供一个可计算的替代量 ​

从 $r$ 做DFS理路深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。，按首次访问顺序赋予编号 $\mathrm{dfn}(v)=1,\dots ,n$，入口编号为 1。记 DFS 父节点为 $\mathrm{parent}(v)$。

对 $w\ne r$，考虑所有这样的路径：

其中每个内部节点都满足 $\mathrm{dfn}(v_i)>\mathrm{dfn}(w)$。在这些路径的起点中，DFS 编号最小的节点叫 $w$ 的半支配点 $\mathrm{sdom}(w)$。

一条直接边没有内部节点，所以每个前驱都可以作为候选起点。DFS 父边又保证半支配点的编号小于 $w$ 的编号。进一步可证明，半支配点是 $w$ 的一个严格 DFS 祖先。

半支配点只要求存在一条特殊路径；支配点却要求所有入口路径都经过它。存在量词与全称量词不同，所以两个概念不能直接合并。

一个半支配点不等于立即支配点的图 ​

取边集

并让 DFS 按 $r,a,b,c$ 的顺序访问。DFS 树是一条链 $r\to a\to b\to c$。

对 $c$，直接边 $a\to c$ 证明 $a$ 是半支配候选；入口到 $c$ 的路径 $r\to b\to c$ 却不能让 $r$ 成为半支配候选，因为内部节点 $b$ 的编号 3 小于 $c$ 的编号 4。因此

然而 $r\to b\to c$ 绕过了 $a$，$r\to a\to c$ 又绕过了 $b$，所以 $\mathrm{idom}(c)=r$。完整结果为：

这个四点例子也会真正触发 LT 的最后修正过程，因而比所有半支配点都恰好正确的树形例子更适合检查实现。

同一控制流图的 DFS 树可以是一条链，支配树却是以入口为中心的星形；DFS 祖先关系不能代替支配关系。

LINK 与 EVAL：查询的是路径最小值 ​

算法按 DFS 编号逆序处理节点。处理过的节点会用 LINK(parent[w], w) 接回 DFS 父节点，形成一组动态祖先链。

对已链接的 $v$，EVAL(v) 返回当前森林中从 $v$ 向上、不包含未链接森林根的路径上，使 semi 最小的代表节点。若 $v$ 本身尚未链接，则直接返回 $v$。路径压缩需要同时维护这个最小值，不能只返回森林根。

以下是简单 LINK 配合路径压缩的版本；NIL 表示没有父指针：

LINK(p, v):
    ancestor[v] = p

COMPRESS(v):
    a = ancestor[v]
    if a != NIL and ancestor[a] != NIL:
        COMPRESS(a)
        if semi[label[a]] < semi[label[v]]:
            label[v] = label[a]
        ancestor[v] = ancestor[a]

EVAL(v):
    if ancestor[v] == NIL:
        return v
    COMPRESS(v)
    return label[v]

压缩时先处理上方路径，再比较两个代表的 semi，最后缩短指针。这里与并查集理路并查集Disjoint-set union · Union-find维护不交集合划分并支持合并与代表元查询的数据结构。相似的是路径压缩机制；要维护的却是带权祖先路径信息，而不是仅仅判断两个元素是否属于同一集合。

补充示意图

这幅补充图使用另一组边，DFS 编号为 $r:1,a:2,c:3,d:4,b:5$。路径 $r\to b\to c$ 的内部点编号 $5>3$，所以这里 $\mathrm{sdom}(c)=r=\mathrm{idom}(c)$；它与前面四点例子中需要最终修正的情况不同。

逆序计算、桶处理与正序修正 ​

DFS 完成后，对全部可达节点初始化 semi[v]=dfn[v]、label[v]=v、ancestor[v]=NIL、桶为空。只把可达前驱加入 pred[v]。入口不参与以下逆序循环。

for i = n, n-1, ..., 2:
    w = vertex[i]

    for v in pred[w]:
        u = EVAL(v)
        semi[w] = min(semi[w], semi[u])

    bucket[vertex[semi[w]]].append(w)
    p = parent[w]
    LINK(p, w)

    for v in bucket[p]:
        u = EVAL(v)
        if semi[u] < semi[v]:
            dom[v] = u
        else:
            dom[v] = p
    bucket[p].clear()

for i = 2, 3, ..., n:
    w = vertex[i]
    if dom[w] != vertex[semi[w]]:
        dom[w] = dom[dom[w]]

扫描前驱时，尚未处理的前驱返回自身，提供直接边候选；已经处理的前驱通过 EVAL 概括相应已链接路径上的半支配信息。原论文的半支配递推定理保证，这些候选正好覆盖定义所需的最小值。

桶负责“到时再算”。节点 $v$ 刚算出半支配点 $s$ 时，不一定已经具备从 $v$ 到 $s$ 的完整查询路径，因此先放入 bucket[s]。随着逆序处理和链接进行，轮到查询这条路径时，才把它转换为直接答案或待修正候选。

这一转换由下面的定理支撑。令 $s=\mathrm{sdom}(w)$，在 DFS 树路径 $(s,w]$ 上取半支配编号最小的节点 $u$，则

由于 $w$ 本身也在路径里，最小值不会比 semi[w] 更大。这正对应桶中的两种分支。第二种情形先记录 $u$，随后正序遍历时，它所依赖的较早节点已经得到修正，因此可以执行 dom[w]=dom[dom[w]]。这不是可以随意省略的压缩优化，而是算法正确性的一部分。[1]

四点例子中的延迟发生在哪里 ​

处理 $c$ 时，得到 semi[c]=dfn(a)=2，把 $c$ 放进 $a$ 的桶。处理 $b$ 后，$b$ 的半支配点已知为 $r$，并且 $c\to b\to a$ 的动态祖先路径已经接好。

这时处理 $a$ 的桶，EVAL(c) 在排除根 $a$ 的路径 $c,b$ 上找到半支配编号更小的 $b$，因此先令 dom[c]=b。这个暂存值尚不是答案。

逆序阶段结束时，$b$ 的最终立即支配点是 $r$。正序修正发现 dom[c]=b 与 sdom(c)=a 不同，于是令 dom[c]=dom[b]=r，与所有入口路径的定义完全一致。

复杂度取决于 LINK 的具体实现 ​

设已抽出的可达子图有 $n$ 个节点、$m$ 条弧，节点已压成连续编号；下面先计算这一核心问题的成本。DFS、前驱扫描和桶中元素的处理次数都是线性的；主要成本来自带最小值维护的路径查询。

上面展示的简单 LINK 加路径压缩版本具有 $O((m+n)\log (n+1))$ 的经典时间上界。原论文进一步给出更精细、带平衡维护的链接实现，将时间改进到 $O((m+n)\alpha (m+n,n))$ 量级，其中 $\alpha$ 是反 Ackermann 型函数。[1]

这两个版本不能混写。普通并查集“按秩合并加路径压缩”的近线性结论，也不能仅因代码里出现路径压缩，就自动移植到 LT 的简单链接过程。若文章给出的是简单 ancestor[v]=p，应报告与它匹配的上界。

存储可达子图与其前驱表使用 $O(m+n)$ 空间；核心辅助数组和桶总共使用 $O(n)$ 空间。若原始输入另含不可达顶点，记原规模为 $N,M$；读取完整输入、建立可达子图及编号映射可另计 $O(N+M)$ 时间与存储，不能用较小的 $n,m$ 隐去这些成本。递归 DFS 和递归 COMPRESS 在长链上还可能达到线性调用深度，工程实现可以改写为显式栈，而不改变算法的数学含义。

与相邻概念及应用的区别 ​

强连通分量理路强连通分量算法Strongly connected components algorithm在线性时间内把有向图划分为互相可达的极大顶点集合。描述节点之间能否互相到达；支配关系描述从指定入口出发是否有绕行路径。改变入口可以改变支配树，却不改变原图的强连通分量。low-link理路Low-link 值Low-link value · LowlinkDFS 子树通过树边和受允许的非树边能够到达的最早发现时间摘要。也使用 DFS 最小编号信息，但其路径约束和目标与半支配点不同，不能把两个数组按名字相似直接替换。

在编译器中，支配树支持支配边界理路支配边界Dominance frontier · DF · 支配前沿收集某节点的支配影响首次可能在控制流汇合处停止的节点，为 SSA 合流定义定位。与SSA 构造理路SSA 构造算法SSA construction algorithm · Dominance-based SSA construction · SSA 重命名先以迭代支配边界插入 φ，再沿支配树用每变量版本栈重命名定义、使用和前驱边参数。。例如一个定义要支配某次使用，才能保证每条到达该使用的控制流路径都已经经过定义。不可达代码应按编译器约定另行处理，不能让“根本没有入口路径”的空真命题污染通常的支配树。

后支配关系常通过反转边、从出口分析得到。多个正常出口可以连接到一个虚拟出口；但无法到达出口的无限循环区域，需要单独说明语义。只对终止路径定义后支配，与把无限执行也纳入路径量词，并不总是同一个概念。

检验实现时，小图上按“删除候选节点后是否仍可到达”直接求支配关系，是一个与 LT 内部机制不同的可靠对照。测试应包含交叉边、回边、多前驱、不可达节点，以及上述半支配点不等于立即支配点的例子，而不只是几棵树。