问题描述
这个问题是有关，但不一样的one最近这里问。
This question is related to but not the same as the one recently asked here.
我刚刚看了<一href="http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#The_algorithm_in_pseudo$c$c"相对=nofollow>维基百科伪code 。
algorithm tarjan is
input: graph G = (V, E)
output: set of strongly connected components (sets of vertices)
index := 0
S := empty
for each v in V do
if (v.index is undefined) then
strongconnect(v)
end if
end for
function strongconnect(v)
// Set the depth index for v to the smallest unused index
v.index := index
v.lowlink := index
index := index + 1
S.push(v)
// 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 is in S) then
// Successor w is in stack S and hence in the current SCC
v.lowlink := min(v.lowlink, w.index)
end if
end for
// If v is a root node, pop the stack and generate an SCC
if (v.lowlink = v.index) then
start a new strongly connected component
repeat
w := S.pop()
add w to current strongly connected component
until (w = v)
output the current strongly connected component
end if
end function
我显然不能明白它正确的，因为我有两个非常基本的问题：
I obviously mustn't have understood it properly since I have two very basic questions:
-
当我们说
如果（w是在S），那么是不是O（N），该操作或至少O（logN）的复杂性，因为元素由其指标进行排序？我们将必须执行此从根节点访问的每一个新的节点，所以没有整体的复杂性O（NlogN）。此外S是一个堆栈所以概念上只有顶级元素应该是可访问的，我们怎么实现它的搜索？如果不是二叉搜索树是一个更好的数据结构在这里？
When we say
if (w is in S), then isn't this operation of O(N) or atleast O(logN) complexity because the elements shall be ordered by their indices? We will have to perform this for each new node accessible from the root node, so isn't the overall complexityO(NlogN). Moreover S is a stack so conceptually only the top element should be accessible, how do we implement search in it? Shouldn't a binary search tree be a better data structure here?
在此部分：
否则，如果（W是S），然后
v.lowlink：= MIN（v.lowlink，w.index）
else if (w is in S) then
v.lowlink := min(v.lowlink, w.index)
有特殊原因使用 w.index ，而不是 w.lowlink ？使用的好处 w.lowlink 将是它会回答previous问题（链接的问题）。该 LLS 在一个SCC将保证是相同的所有节点的所有节点。
Is there a specific reason for using w.index and not w.lowlink? The advantage for using w.lowlink would be that it would answer the previous question (the linked question). The LLs for all the nodes in an SCC would guaranteed be the same for all nodes.
推荐答案
1）你的第一个问题：它可以很容易地为O已完成（1），只是维持一个布尔数组 inStack ，那一刻的节点 N 放在堆栈，标志 inStack [N] 为true。当你的流行从堆栈，其标记为false。
1) Your first question: It can easily been done in O(1) , just maintain a boolean array inStack, the moment node n is put in the stack, flag inStack[n] to true. When you pop it off the stack, flag it back to false.
2）的 w.index 没有太大的不同， w.lowlink ，但是这是更容易阅读，因为我们就会明白，这种情况是检查从节点A的情况下 - 乙 - ç - > A，其中检查时节点C可达到predecessor节点A与否。请记住，目前我们更新C，节点A lowlink不更新正确呢。
2) Not much different between w.index and w.lowlink , but this is easier to read, as we will understand that this condition is to check for the case from Node A ->B ->C ->A, which checking when node C can reach a predecessor node A or not. Keep in mind that at the moment we updating C, node A lowlink is not updated properly yet.
的的Tarjan算法是基于这样的事实：一个节点将是一个SCC的根当且仅当从该节点，就不能达到任何predecessor节点（这意味着它有在它的SCC最低lowlink和也等于该节点的指数）。因此，条件是在实现这个想法的最直接的方式，如果我们遇到一个已经访问过的一个节点，我们检查这个节点是否是当前节点与否的predecessor（这是由它的索引确定，也此节点的图中的水平）
The Tarjan algorithm is based on the fact that a node will be the root of a SCC if and only if from that node, we cannot reach any predecessor node (which means it has the lowest lowlink in its SCC and also equals to this node's index). So the condition is just implemented this idea in the most straight forward way, if we encounter a node that is already visited, we check whether this node is a predecessor of the current node or not (which is determined by its index , also the level of this node in the graph)
这篇关于的Tarjan的算法：时间复杂度和细微的修改可能性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！