Tarjan 的强连通分量算法——为什么索引在后边？

Question

我正在研究 Tarjan's algorithm for strongly-connected components，我很清楚它的工作方式。无论如何，有一行我不明白：

// Consider successors of v
for each (v, w) in E do
  if (w.index is undefined) then
    // Successor w has not yet been visited; recurse on it
    strongconnect(w)
    v.lowlink  := min(v.lowlink, w.lowlink)
  else if (w.onStack) then
    // Successor w is in stack S and hence in the current SCC
    v.lowlink  := min(v.lowlink, w.index) // *************
  end if
end for

我用星号标记了这一行。遇到后缘

为什么要取节点的发现index/time

v.lowlink  := min(v.lowlink, w.index)

而不是仅仅获取其组件值？

v.lowlink  := min(v.lowlink, w.lowlink)

我想不出这会成为问题的情况。

有人能赐教吗？编辑：我怀疑这只是一个语义要求，即 lowlink 被定义为从具有 只有一个后缘 的节点可到达的最早祖先，但这只是一个大胆的猜测。

Answer 1

如果 w.lowlink 至少是从 w 可到达的最低索引并且至多是从 w 使用最多一个后边可到达的最低索引，则正确性证明通过。组件检测只需要我们知道是否可以 "escape" 到较低的索引。

它以这种方式呈现的原因可能是人们可以想象 lowlink 仅按 post 顺序设置，然后您的变体将无法很好地定义。（维基百科伪代码预先将其初始化为 index。）

Tarjan 的强连通分量算法——为什么索引在后边？

Tarjan's strongly-connected components algorithm - why index in the back edge?

language-agnostic

algorithm

graph

directed-graph

tarjans-algorithm