algorithm - Tarjan 算法中的交叉链接

Question

我正在阅读 Tarjan's paper on scc .

在论文中，给定顶点的lowlink定义为:

LOWLINK (v) is the smallest vertex which is in the same component as v and is reachable by traversing zero or more tree arcs followed by at most one frond or cross-link.

我想不出任何情况下给定 scc 中的两个顶点通过交叉链接边缘，因为整个 scc 应该在 dfs 搜索派生的一棵树中。谁能稍微解释一下？

Answer 1

这个想法很简单:

您在遍历图形时为图形编制索引，当您从递归返回时，为每个节点记下从中可以到达的最小索引。要达到低于指定节点已有的索引，必须有一个交叉链接或叶链接。因为当你到达一个索引较低的尚未打开的节点时，这意味着你在同一个 scc 中找到了一个节点，很容易理解，所有具有相同 lowlink 的节点都在同一个组件中( visualization of the algorithm )。