如何学习Tarjan算法？

Question

我已经尝试从维基百科学习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是一个根节点？

有人能否向我解释一下这个算法背后的直觉或动机？

- Nihal

---

抱歉链接失效了，不知道怎么让它工作。请直接复制整个链接。 - Nihal

已修复损坏的链接；使用“地球仪”图标在选定的文本上使用特定的URL。 :) - Akarun

这个网址 https://dev59.com/FGw15IYBdhLWcg3wZq1q 对你有帮助吗？ 有时看实际代码比伪代码更容易理解。 - Dave

帮助不大。还是谢谢。 - Nihal

哦，看起来dfs标签指的是其他东西。 - Nihal

Answer 1

这个想法是：在遍历树时，每次搜索完一个分支并回溯时，检查是否遇到了指向树中“上层”节点的边。

• 如果没有（if (v.lowlink = v.index)），那么你刚刚完成了一个SCC - 它由当前节点和栈中所有节点组成。除了已经完成的SCC中的节点之外，它恰好是DFS树的一个子树。

• 如果有，你将此信息传播到“上层”节点（v.lowlink := min(v.lowlink, w.lowlink)），因为结合DFS树中的路径，该边创建了一条“向上”的路径。

DFS生成一棵森林，但你总是一次考虑一棵树。SCC始终包含在一个DFS树中，否则（作为SCC）这将存在两个方向的路径连接涉及的树中的所有树 - 这是矛盾的。

- voidengine

---

我只是无法想象这里的回溯。 - Trajan

Answer 2

补充pjotr的回答：v.lowlink基本上是您在树中找到的最上面节点的索引。请记住，在此情况下，最上面的意思是最小值，因为随着向下走，索引不断增加。现在，在处理所有后继之后，基本上有三种情况：

1. v.lowlink < v.index: 这表示你找到了一条反向边。请注意，我们不仅找到了任何一条反向边，而是找到了指向“上方”节点的一条反向边。这就是v.lowlink < v.index的含义。

2. v.lowlink = v.index: 在这种情况下，我们知道没有反向边指向当前节点以上的任何内容。可能有一条反向边指向该节点（这意味着您的某个后继节点w具有低链接，使得w.lowlink = v.lowlink = v.index）。也可能存在一条反向边，指向当前节点以下的内容，这意味着已经打印出了一个强连通分量。无论如何，当前节点肯定也是一个强连通分量的根。

3. v.lowlink > v.index: 实际上不可能发生。我只是为了完整性而列出它。 ;)

希望对您有所帮助！

- bhuemer

Answer 3

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的根。

希望这有所帮助。

- Sumit Trehan

Answer 4

掌握桥和关节点算法的路径

• 观看this视频，让你感受到你已经非常理解这个算法。
  
• 从这里和这里练习该算法。
• 练习问题以掌握它：
  • A. Cutting Figure
  • EC_P - Critical Edges
  • SUBMERGE - Submerging Islands
  • POLQUERY - Police Query

- Ganesh Chowdhary Sadanala