我正在学习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)
我想不出这会成为问题的情况。
有人能给我解释一下吗? 编辑:我怀疑这只是语义上的要求,即lowlink被定义为从具有仅一个反向边的节点可达的最早祖先,但这只是一个猜测。