我正在阅读Tarjan 关于 scc 的论文。
在论文中，给定顶点的低链接定义为：
LOWLINK (v) 是与 v 位于同一组件中的最小顶点，可以通过遍历零个或多个树弧后跟最多一个叶子或交叉链接来到达。
我无法通过交叉链接边缘从给定 scc 中的两个顶点的路径想出任何情况，因为整个 scc 应该位于由 dfs 搜索派生的一棵树中。谁能解释一下？
问问题
374 次
1 回答
0
The idea is simple:
You index the graph as you traverse it, when you are returning from the recursion, you note for each node, which least index is reachable from it. To reach lower index than the specified node already has, there has to be a cross link or a frond link. Because when you reach an yet open node with lower index, it means that you have found a node in the same scc, it is easy to follow, that all nodes with the same lowlink are in the same component (visualization of the algorithm).
于 2013-02-05T07:59:50.503 回答