如何在图中找到强连通分量？

Question

我正在尝试自学图论，并且现在正在尝试理解如何在图中找到强连通分量。我已经阅读了 SO 上的几个不同的问题/答案（例如，1,2,3,4,5,6,7,8），但我找不到一个具有完整逐步示例的答案可以供我参考。

根据CORMEN（算法导论），一种方法是：

1. 调用DFS(G)计算每个顶点u的完成时间f[u]
2. 计算G的转置
3. 调用DFS(Transpose(G))，但在DFS的主循环中，按照f[u]递减的顺序考虑顶点
4. 将步骤3的深度优先森林中每棵树的顶点作为单独的强连通分量输出

观察以下图形（问题3.4来自这里。我已经在这里和这里找到了几个解决方案，但我正在尝试分解并自己理解它。）

Step 1: 调用DFS(G)计算每个顶点u的结束时间f[u]。

运行以A为起点的DFS：

请注意以 [Pre-Visit，Post-Visit] 格式呈现的红色文本。

步骤2：计算 G 的转置

第三步：调用DFS(Transpose(G))，但在DFS的主循环中，按照f[u]（如步骤1中计算的）递减的顺序考虑顶点

好的，按照后序遍历（完成时间）值递减的顺序考虑顶点：

{E, B, A, H, G, I , C, D, F ,J}

因此，在这一步中，我们在G^T上运行DFS，但从以上列表中的每个顶点开始：

• DFS(E)：{E}
• DFS(B)：{B}
• DFS(A)：{A}
• DFS(H)：{H, I, G}
• DFS(G)：从列表中删除，因为它已经被访问过了
• DFS(I)：从列表中删除，因为它已经被访问过了
• DFS(C)：{C, J, F, D}
• DFS(J)：从列表中删除，因为它已经被访问过了
• DFS(F)：从列表中删除，因为它已经被访问过了
• DFS(D)：从列表中删除，因为它已经被访问过了

第四步：将第三步深度优先森林中每个树的顶点作为一个单独的强连通分量输出。

所以我们有五个强连通分量：{E}，{B}，{A}，{H，I，G}，{C，J，F，D}

我认为这是正确的。然而，我在这里和这里找到的解决方案说SCCs是{C,J,F,H,I,G,D}和{A,E,B}。我的错误在哪里？

- lucidgold

---

看一下 B 和 E：它们的入度都为零，并且自己形成了一个（退化的）强连通分量。我认为链接的答案是错误的。（比我快了40秒。） - greybeard

我相信你提供的来源中给出的答案是错误的，尽管两种实现都是正确的。我已经实现了他们正在使用的算法，我的算法给出了你得出的答案。我猜他们在某个地方犯了一个错误，但算法并没有错，无论是你的还是他们的。 - user8147810

Answer 1

您的步骤是正确的，您的答案也是正确的。通过检查您提供的其他答案，您可以看到他们使用了不同的算法：首先在G转置上运行DFS，然后在处理顶点的post编号时以递减顺序在G上运行一个无向组件算法。

问题在于他们在G转置上运行了最后一步，而不是在G上运行，因此得到了错误的答案。如果您从第98页开始阅读Dasgupta，将会看到他们（尝试）使用的算法的详细解释。

- hbejgel

Answer 2

你的答案是正确的。根据CLRS，“有向图G =（V，E）的强连通分量是指最大的顶点集合C，其中对于每对顶点u和v，我们既有u~> v又有v~> u，即顶点v和u彼此可达。”

如果你认为{C，J，F，H，I，G，D}是正确的，那么就没有办法从D到达G（还有许多其他谬论），同样的，如果使用另一个集合，就没有办法从A到达E。

- kaustubh