algorithm - 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

我用星号标记了这一行。为什么遇到后缘要取节点的发现索引/时间

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

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

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

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

请问有没有大佬解惑一下？编辑:我怀疑这只是一个语义要求，即 lowlink 被定义为从具有只有一个后缘的节点可到达的最早祖先，但这只是一个疯狂的猜猜。

Answer 1

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

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