这个问题与one recently asked here相关但不相同.
我刚刚阅读了 Wikipedia psuedocode .
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
显然我一定没有理解正确,因为我有两个非常基本的问题:
当我们说
if (w is in S)
时,这不是 O(N) 或至少 O(logN) 复杂度的操作,因为元素应按它们的顺序排序指数?我们将不得不为每个可从根节点访问的新节点执行此操作,因此总体复杂度不是O(NlogN)
。此外,S 是一个堆栈,因此从概念上讲,只有顶部元素应该是可访问的,我们如何在其中实现搜索?二叉搜索树不应该是更好的数据结构吗?这部分:
else if (w is in S) then
v.lowlink := min(v.lowlink, w.index)
是否有使用 w.index
而不是 w.lowlink
的特定原因?使用 w.lowlink
的好处是它可以回答上一个问题(链接的问题)。 SCC 中所有节点的 LL
将保证所有节点都相同。
最佳答案
1) 你的第一个问题:O(1) 可以很容易地完成,只需要维护一个 bool 数组inStack
,节点n
被放入堆栈的那一刻, 将 inStack[n]
标记为 true。当您将其从堆栈中弹出时,将其标记回 false。
2) w.index
和 w.lowlink
之间没有太大区别,但这更容易阅读,因为我们将理解这个条件是检查来自节点 A ->B ->C ->A 的情况,检查节点 C 何时可以到达前任节点 A。请记住,在我们更新 C 的那一刻,节点 A lowlink 尚未正确更新。
Tarjan 算法基于这样一个事实,即一个节点将成为 SCC 的根当且仅当从该节点我们无法到达任何前任节点(这意味着它在其 SCC 中具有最低的低链路并且也等于该节点的索引)。所以条件只是以最直接的方式实现了这个想法,如果我们遇到一个已经访问过的节点,我们检查这个节点是否是当前节点的前驱(这由它的索引决定,也是级别图中的这个节点)
关于algorithm - Tarjan 的算法 : Time Complexity and slight modification possibility,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24114178/