形式陈述

Low-link 不是一个跨问题完全统一的对象。 在无向图割点/桥算法中，$\mathrm{low}[v]$ 是从 $v$ 的 DFS 子树经若干树边再至多一条返祖边可达的最小发现时间。 在 Tarjan 强连通分量算法中，lowlink 只考虑仍在栈中的活动顶点。两种递推相似，但允许的边与语义不同。

直觉

它压缩了一个 DFS 子树是否能绕过父边“向上逃回”的信息。

例子与边界

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

推论与应用

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

参考资料

• Jeff Erickson, Algorithms (2019/2026 notes), depth-first search and low-link ideas.
• OI-Wiki contributors, OI-Wiki (2026), low-link, bridges, articulation points, SCC.