我如何学习Tarjan的算法? [英] How do I learn Tarjan's algorithm?
问题描述
http://en.wikipedia.org/wiki / Tarjan's_strongly_connected_components_algorithm#cite_note-1
为什么它是DFS树的子树?(实际上DFS生成一个目录林?o_O)
为什么 v.lowlink = v.index
意味着 v
是根?
有人可以向我解释一下/给出这个算法背后的直觉或动机吗?
这个想法是:当遍历树时,每次搜索一个分支并回溯时,检查是否遇到了树中'上'节点的边。-
如果您没有(
if(v.lowlink = v.index)
),我刚刚完成了一个SCC--它由当前节点和堆栈中的所有节点组成,这正是DFS树的一个子树,除了SCC中的节点如果你这样做了,你将这个信息传播到'上面'节点(v.lowlink:= min (v.lowlink,w.lowlink)
),因为与DFS树中的路径相结合,边会创建一个'向上'路径。
DFS生成一个森林,但您始终只考虑一棵树。一个SCC总是包含在一个DFS树中,否则(作为SCC)在两个(所有)树之间都会有一条双向路径 - 这是矛盾的。
I have been trying to learn Tarjan's algorithm from Wikipedia for 3 hours now, but I just can't make head or tail of it. :(
http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1
Why is it a subtree of the DFS tree? (actually DFS produces a forest? o_O)
And why does v.lowlink=v.index
imply that v
is a root?
Can someone please explain this to me / give the intuition or motivation behind this algorithm?
The idea is: When traversing the tree, every time you've searched through a branch and are backtracking, you check whether you've encountered an edge to an 'upper' node in the tree.
If you didn't (
if (v.lowlink = v.index)
), then you've just completed an SCC - it consists of the current node and all nodes on the stack. That's exactly a subtree of the DFS tree, except for the nodes in SCCs that were already completed.If you did, you propagate this information to 'upper' nodes (
v.lowlink := min(v.lowlink, w.lowlink)
), because combined with the path in DFS tree the edge creates an 'upward' path.
DFS produces a forest, but you always consider one tree a time. An SCC is always included in one DFS tree, otherwise (being an SCC) there would be a path in both directions between both (all) trees in question - that's a contradiction.
这篇关于我如何学习Tarjan的算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!