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

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

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

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

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

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

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

Answer 1

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

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