SCC 的 Tarjan 算法

Question

我在SCC的这一部分被绊倒了。我知道5,6,7是强连通分量。从 no 开始执行 SCC 的 tarjan 算法 de 5，我在 7 处得到了不满意的低链接值。

图和DFS树

令 (x,y) ->(id,低链接)

执行DFS（节点5），（5,5）我到达节点6（6,6）。从节点 6 开始，我有两条外相邻边，一条与节点 5 相邻，另一条与节点 7 相邻。假设选择另一条与节点 7 相邻，(7,7)。从节点 7 开始，只有一条外邻边通向已被访问过的节点 6。因此我做了(7,7)到(7,6)的低链接更新。 然后我回溯到节点 6 并探索到节点 5 的外相邻边。因此将 (6,6) 更新为 (6,5)。然后再次回溯到节点 5。

根据 Tarjan 我应该得到 (5,5),(6,5),(7,5) 但我得到了 (5,5),(6,5),(7,6)

我哪里做错了？

Answer 1

强连通分量中所有节点的

low

值必须相同，这是不正确的。只需要强连通分量的 DFS 遍历中访问的第一个节点具有

id[node] == low[node]

即可。强连接组件中的任何其他节点都应该具有

low[node] < id[node]

，因为它可以通过后边缘到达较早的节点。

为了实际处理强连通分量，我们可以在 DFS 遍历中第一次遇到每个节点时将其压入堆栈。一旦我们识别出强连接组件的第一个节点，我们就可以从堆栈中删除所有节点，直到该节点，从而形成强连接组件。