Tarjan算法分步执行疑问：为何用w.index而非w.lowlink？

伪代码回顾 #

先聚焦核心逻辑贴出Tarjan算法的关键伪代码：

function strongconnect(v)
    v.index := index
    v.lowlink := index
    index := index + 1
    S.push(v)
    v.onStack := true
  
    for each (v, w) in E do
        if w.index is undefined then
            strongconnect(w)
            v.lowlink := min(v.lowlink, w.lowlink)
        else if w.onStack then
            // 疑问点：为什么用w.index而非w.lowlink？
            v.lowlink := min(v.lowlink, w.index)
  
    if v.lowlink = v.index then
        // 弹出栈生成SCC
        repeat
            w := S.pop()
            w.onStack := false
            add w to current strongly connected component
        while w ≠ v
        output the current strongly connected component

核心疑问解答 #

1. 为什么用w.index是正确的？

先明确两个不可动摇的定义：

• index：节点被首次访问时的时间戳，一旦赋值永久不会修改。
• lowlink[v]：从v出发，通过树边+最多一条回边（指向当前栈中节点的边），能到达的最小index值。

当遇到w.onStack的情况（w属于当前正在探索的SCC候选集合），用w.index更新v.lowlink完全符合算法逻辑：

• 栈中的w一定属于未完成的当前SCC，它的lowlink最终会收敛到该SCC根节点的index（即该SCC中最小的index）。
• 即使当前用w.index更新，后续通过树边的回溯传递（w处理完所有后继后，会把自己的最终lowlink传递给前驱），v的lowlink会被自动修正到正确的最小值。

2. 你提到的示例分析

你说回溯到顶点5（index=5，lowlink=5）时，其后继是顶点6（index=6，lowlink=2），按伪代码计算min(5,6)还是5，但实际中顶点5的lowlink变成了2。这里的关键是你混淆了两种边的处理顺序：

• 如果顶点6是通过树边（5→6）被首次访问的，那么在递归处理完6的所有后继后，会执行v.lowlink := min(v.lowlink, w.lowlink)（此时v是5，w是6），这一步直接把5的lowlink更新为min(5,2)=2。
• 而如果5→6是一条回边（即6已被访问且在栈中，但不是通过5首次访问的），此时用w.index=6更新不会改变5的lowlink，但5的lowlink早已通过其他路径（比如树边的回溯传递）被更新为2了。

3. 为什么不用w.lowlink？

其实用w.lowlink在大多数场景下也能得到正确结果，但Tarjan原始论文选择w.index有两个核心原因：

• w.index是固定值，不会在后续递归中被修改，逻辑更稳定，避免因w.lowlink未完全更新（比如w还在递归栈中，未处理完所有后继）导致的潜在问题。
• 算法的正确性依赖于lowlink的定义，用w.index更贴合“回边直接指向栈中节点的原始访问时间戳”这一逻辑，保持了算法的严谨性。

内容的提问来源于stack exchange，提问作者pfeidewigo100