phi*_*ane 14 graph depth-first-search tarjans-algorithm
我一直试图从维基百科学习Tarjan的算法3个小时,但我无法做出它的头或尾.:(
http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1
为什么它是DFS树的子树？(实际上DFS会产生一个森林？o_O)为什么v.lowlink=v.index暗示这v是一个根？
有人可以向我解释这个/给出这个算法背后的直觉或动机吗？
voi*_*ine 14
这个想法是:当遍历树时,每次你搜索一个分支并回溯时,你会检查你是否遇到了树中"上"节点的边缘.
如果你没有(if (v.lowlink = v.index)),那么你刚刚完成了一个SCC - 它由当前节点和堆栈上的所有节点组成.这正是DFS树的子树,除了SCC中已经完成的节点.
如果这样做,则将此信息传播到"上部"节点(v.lowlink := min(v.lowlink, w.lowlink)),因为与DFS树中的路径结合,边缘会创建"向上"路径.
DFS生成一个森林,但您总是一次考虑一棵树.SCC总是包含在一个DFS树中,否则(作为SCC)在所讨论的两个(所有)树之间将存在两个方向上的路径 - 这是矛盾的.
小智 10
只是添加到pjotr的答案:v.lowlink基本上是您在树中找到的最高节点的索引.请记住,在这种情况下,最重要的是最小,因为当你走下去时你会不断增加指数.现在处理完所有后继者后,基本上有三种情况:
v.lowlink <v.index:这表示您找到了后缘.请注意,我们不仅发现了任何后沿,而是指向一个位于当前节点"上方"的节点.这就是v.lowlink <v.index所暗示的.
v.lowlink = v.index:在这种情况下我们知道的是没有后边缘引用当前节点之上的任何内容.此节点可能存在后沿(这意味着您的一个后继节点w具有低链接,使得w.lowlink = v.lowlink = v.index).也可能是有一个后边缘指的是当前节点下面的东西,这意味着当前节点下面已经打印出一个强连接的组件.但是,当前节点肯定也是强连接组件的根.
v.lowlink> v.index:这实际上是不可能的.我只是为了完整性而列出它.;)
希望能帮助到你!