我一直在努力，现在学习维基百科的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为根？
是否有人可以给我讲解一下/给这个算法背后的直觉或动机是什么？
Answer 1:
我们的想法是：当遍历树，每次你通过一个分支搜索，并回溯时间，您检查是否遇到了一个边缘到树的“上部”节点。
如果你没有（
if (v.lowlink = v.index)那么你刚刚完成的SCC -它由当前节点和栈上的所有节点。 这也正是DFS树的子树，除了已经完成，在SCC的节点。如果是这样，您传播该信息来“上部”节点（
v.lowlink := min(v.lowlink, w.lowlink)因为在DFS树中的边缘创建一个“向上”路径的路径组合。
DFS产生了森林，但你总是认为一棵树的时间。 一个SCC总是包含在一个DFS树，否则（作为一个SCC）也就会在这两个问题（全部）树之间两个方向的路径 - 这是一个矛盾。
Answer 2:
只是增加了pjotr的回答是：v.lowlink基本上是您在树中发现的最上方节点的索引。 请记住，在这种背景下至上意味着最低为你不断增加指数当你走。 现在处理所有的继任者后，有三个基本情况：
v.lowlink <v.index：这表明你已经找到了底部。 需要注意的是，我们还没有刚发现任何回力，而是一个指向是“上面”目前的一个节点。 这是v.lowlink <v.index意味着什么。
v.lowlink = v.index：我们知道在这种情况下，什么是没有回边缘指的是当前节点高于一切。 有可能是一个后缘，该节点（这意味着你的继任者的一个节点W具有lowlink这样w.lowlink = v.lowlink = v.index）。 它也可能是，有一个后边缘指某物当前节点之下，这意味着有已经打印出已经在当前节点之下的强连接组件。 当前节点，但是，绝对是强连接组件的根为好。
v.lowlink> v.index：这实际上是不可能的。 我刚上市它完整的缘故。 ;）
希望能帮助到你！
Answer 3:
直觉性有关的Tarjan的算法：
DFS期间，当我们从顶点v遇到一个后边缘，我们更新其最低可达祖先即我们更新的值低[V]
现在，当所有顶点的出射边缘被处理，即我们将要退出DFS呼叫的顶点v，我们检查的值低[V]，是否低[V] == V（下面说明）。 如果没有这意味着v不是SCC的根源，我们现在请利于V的母公司即父的最低可达祖先[V]现在变为低[V]。
这听起来逻辑如果虽然有作为从父[V]到v的祖先没有直接的后边缘，但有通过该父[V]仍然可以到达的路径（V +朝向V边缘的后边缘）诉祖先。因此，我们也更新了低[父[v]在这里。 因此，我们将不断更新这个链条和低[V]为所有的V将不断更新，直到我们达到祖先（通过回溯）。 对于这种低祖先[V]将等于诉因此该将作为SCC的根。
希望这可以帮助
文章来源: How do I learn Tarjan's algorithm?
