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

Question

我正在研究用于强连接组件的 Tarjan 算法，它的工作方式对我来说很清楚。无论如何，有一行我不明白：

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

我用星号标记了这条线。遇到back-edge时为什么要取节点的发现索引/时间

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

而不是仅仅抓住它的组件价值？

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

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

有人可以启发我吗？编辑：我怀疑这只是一个语义要求，即 lowlink 被定义为从只有一个 back-edge的节点可到达的最早祖先，但这只是一个疯狂的猜测。

Answer 1

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

可能它以这种方式呈现的原因是人们可以想象lowlink只能在后序中设置，然后你的变体就不会被很好地定义。（维基百科伪代码将其初始化为index。）