我已经尝试从 Wikipedia 学习 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是一个根？
有人可以向我解释一下/给出这个算法背后的直觉或动机吗？
问问题
14531 次
4 回答
15
这个想法是：在遍历树时，每次搜索分支并回溯时，都要检查是否遇到了树中“上”节点的边。
如果您没有 (
if (v.lowlink = v.index))，那么您刚刚完成了一个 SCC - 它由当前节点和堆栈上的所有节点组成。这正是 DFS 树的子树，除了 SCC 中已经完成的节点。如果这样做，则将此信息传播到“上”节点（
v.lowlink := min(v.lowlink, w.lowlink)），因为与 DFS 树中的路径相结合，边缘会创建“向上”路径。
DFS 产生一片森林，但您总是一次只考虑一棵树。一个 SCC 总是包含在一个 DFS 树中，否则（作为一个 SCC）在两个（所有）树之间会有一条双向路径 - 这是一个矛盾。
于 2012-06-13T14:03:06.167 回答
11
只是添加到 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：这实际上是不可能的。为了完整起见，我只是列出它。;)
希望能帮助到你！
于 2013-02-25T21:46:17.800 回答
1
关于 Tarjan 算法的一些直觉：
在 DFS 期间，当我们遇到来自顶点 v 的后边时，我们更新它的最低可达祖先，即我们更新 low[v] 的值
现在当一个顶点的所有出边都处理完毕，即我们即将退出对顶点v的DFS调用时，我们检查low[v]的值，是否low[v] == v（解释如下）。如果不是，这意味着 v 不是 SCC 的根，我们现在将好处赋予 v 的父级，即 parent[v] 的最低可达祖先现在更改为 low[v]。
这听起来很合乎逻辑，好像虽然从 parent[v] 到 v 的祖先没有直接的后沿，但是有一条路径（v 的后沿 + 到 v 的边）仍然可以通过它 parent[v] 到达v 的祖先。因此我们在这里也更新了 low[parent[v]]。因此，我们将继续更新这条链，并且所有 v 的 low[v] 将继续更新，直到我们到达祖先（通过回溯）。对于这个祖先，low[v] 将等于 v。因此这将作为 SCC 的根。
希望这可以帮助
于 2014-05-17T05:55:28.377 回答