Tarjan的紧密连接组件算法-为什么在后边缘进行索引? [英] Tarjan's strongly-connected components algorithm - why index in the back edge?

问题描述

我正在研究 Tarjan用于强连接组件的算法及其工作方式对我很清楚无论如何，我不明白这句话:

I'm studying Tarjan's algorithm for strongly-connected components and the way it works is clear to me. Anyway there's a line I don't understand:

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

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

I marked the line with asterisks. Why should we take the discovery index/time of a node when encountering a back-edge

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

不仅仅是获取其组件价值?

rather than just grabbing its component value?

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

我想不出这是个问题的情况.

I can't think of a case where this would be a problem.

有人可以启发我吗?我怀疑这只是一个语义要求，即lowlink被定义为可以从具有一个后沿的节点访问的最早祖先，但这只是一个疯狂的选择猜.

Can someone enlighten me please? I suspect this is only a semantic requirement, i.e. lowlink being defined as the earliest ancestor reachable from the node with only one back-edge, but this is just a wild guess.

推荐答案

如果 w.lowlink 至少是从 w 可访问的最低索引，并且最多使用一个后边缘从 w 可以访问的最低索引.组件检测仅要求我们知道是否可以转义"到较低的索引.

The correctness proof goes through if w.lowlink is at least the lowest index reachable from w and at most the lowest index reachable from w using at most one back edge. Component detection just requires us to know if we can "escape" to a lower index.

之所以以这样的方式呈现它，可能是因为人们可以想象 lowlink 只能以后期顺序设置，然后您的变体形式就无法很好地定义.(Wikipedia伪代码将其预先初始化为 index .)

Probably the reason that it's presented the way that it is is that one can imagine lowlink only being set in post-order, and then your variation wouldn't be well defined. (The Wikipedia pseudocode initializes it in pre-order to index.)

这篇关于Tarjan的紧密连接组件算法-为什么在后边缘进行索引?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！