我如何学习Tarjan的算法?

问题描述 投票:14回答:4

我已经尝试了3个小时,从Wikipedia学习Tarjan的算法,但是我无法做到此事。 :(

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1

为什么它是DFS树的子树? (实际上DFS会产生森林吗?o_O)为什么v.lowlink=v.index暗示v是根?

有人可以向我解释一下/给出该算法背后的直觉或动机吗?

graph depth-first-search tarjans-algorithm
4个回答
14
投票

想法是:遍历树时,每次遍历分支并进行回溯时,您都要检查是否遇到树中“上”节点的边缘。

  • 如果您没有(if (v.lowlink = v.index)),则您刚刚完成了一个SCC-它由当前节点和堆栈上的所有节点组成。除了已经完成的SCC中的节点外,这就是DFS树的子树。

  • 如果您这样做,则将此信息传播到“上层”节点(v.lowlink := min(v.lowlink, w.lowlink)),因为结合DFS树中的路径,边缘将创建“上层”路径。

DFS产生一个森林,但是您每次总是考虑一棵树。一棵DFS树中始终包含一个SCC,否则(成为SCC)这两个(所有)树之间会在两个方向上都有一条路径-这是矛盾的。


10
投票

只是添加到pjotr的答案中:v.lowlink基本上是您在树中找到的最高节点的索引。请记住,在这种情况下,最高价意味着最低价,因为您走下坡路时会不断增加指数。现在,在处理完所有继任者之后,基本上有以下三种情况:

  1. v.lowlink

  2. v.lowlink = v.index:在这种情况下,我们知道的是,没有后边缘引用当前节点上方的任何内容。此节点可能有一个后边缘(这意味着您的后继节点之一w具有低链接,从而w.lowlink = v.lowlink = v.index)。也可能是后边缘指向当前节点下方的某物,这意味着当前节点下方存在已被打印出的牢固连接的组件。但是,当前节点也绝对是牢固连接的组件的根。

  3. v.lowlink> v.index:实际上是不可能的。为了完整起见,我只列出它。 ;)

希望有帮助!


1
投票

关于Tarjan算法的一些直觉:

  • 在DFS期间,当遇到顶点v的后边缘时,我们更新其最低可达祖先,即,我们更新low [v]

  • 的值
  • 现在,当处理了顶点的所有输出边缘时,即我们即将退出顶点v的DFS调用时,我们将检查low [v]的值,是否low [v] == v(说明下面)。如果不是这样,则意味着v不是SCC的根,我们现在将利益提供给v的父级,即,parent [v]的最低可达祖先现在更改为low [v]。

这听起来似乎很合理,尽管似乎没有从父代[v]到v祖先的直接后沿,但是有一条路径(v的后沿+朝v的边缘)仍然可以通过父代[v]达到v的祖先。因此,我们也在此处更新了low [parent [v]]。因此,我们将继续更新此链,对于所有v,low [v]将继续更新,直到我们到达祖先(通过回溯)。对于此祖先,low [v]将等于v。因此,它将作为SCC的根。

希望这会有所帮助


0
投票

掌握网桥和发音算法的路径

© www.soinside.com 2019 - 2024. All rights reserved.