Low-link 值

Low-link 值概括 DFS 子树能否绕过父边，并通过至多一条返祖边“向上逃回”到某个最早发现时间。它把许多后代的回边信息向父节点聚合，使“删掉父边后子树还能否回到祖先”变成一个整数比较。无向图的桥/割点与有向图 Tarjan SCC 都使用类似记号，但更新规则不同，不能共享一段未经区分的代码。

无向图中遇到已访问邻点时必须排除当前父边的对应边；多重边会使“按父顶点排除”出错，应按边 ID 处理。不能把 SCC lowlink 的栈条件省略。

无向 DFS 中，树边 $(u,v)$ 是桥当且仅当 $low[v]>tin[u]$：这说明 $v$ 子树没有返祖边抵达 $u$ 或更早祖先。若 $low[v]\ge tin[u]$，非根 $u$ 是割点候选；根需至少两个 DFS 子树才是割点。

遇到父边不能按普通已访问边更新 low，平行边场景还需用边 ID 区分“那一条父边”和另一条返边。有向 SCC 算法只用指向当前栈内顶点的边更新，指向已出栈分量的边不应影响 low。

它统一解释桥、割点、边双连通分量和 Tarjan SCC 的关键不变量，同时明确这些算法不可混用的边界。

深度优先搜索公理库深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。 提供树与发现时间，图公理库有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。 和 有向图公理库有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。 产生不同版本。它支撑桥、割点、双连通分量和 强连通分量公理库强连通分量算法Strongly connected components algorithm在线性时间内把有向图划分为互相可达的极大顶点集合。 的线性时间算法。

Low-link 值依一次静态 DFS 树及未更新边集。全动态连通公理库全动态连通性Fully dynamic connectivity · Dynamic graph connectivity以分层生成森林和 replacement-edge 搜索维护在线边插入删除下的无向图连通性，并用边层级单调提升证明多对数摊还更新界。在边插删后维护生成森林和替代边，不能局部改几个 low 值继续使用原 DFS。Dominator Tree / Lengauer–Tarjan公理库支配树与 Lengauer–Tarjan 算法Dominator tree · Lengauer–Tarjan algorithm · 支配树在单入口流图中用 DFS 半支配点、延迟桶处理和带路径压缩的祖先查询计算立即支配点与支配树。也使用 DFS 编号和半支配量，但解决有向流图“所有入口路径必经”关系，不是 low-link 在有向图上的直接推广。