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

Question

我正在尝试自学图论，现在想了解如何找到 SCC在图表中。我已经阅读了几个关于 SO 的不同问题/答案(例如 1、2、3、4、5、6、7、8)，但我找不到一个带有我可以遵循的完整分步示例的示例。

根据 CORMEN (Introduction to Algorithms) ，一种方法是:

1. Call DFS(G) to compute finishing times f[u] for each vertex u
2. Compute Transpose(G)
3. Call DFS(Transpose(G)), but in the main loop of DFS, consider the vertices in order of decreasing f[u] (as computed in step 1)
4. Output the vertices of each tree in the depth-first forest of step 3 as a separate strong connected component

观察下图(问题是 here. 中的 3.4 我已经找到了几个解决方案 here 和 here ，但我试图分解它并自己理解它。)

第 1 步:调用 DFS(G) 计算每个顶点 u 的完成时间 f[u]

从顶点 A 开始运行 DFS:

请注意格式为 [Pre-Vist, Post-Visit] 的红色文本

第 2 步:计算转置 (G)

第 3 步。调用 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):从列表中删除，因为它已经被访问过

第 4 步:将第 3 步的深度优先森林中每棵树的顶点输出为单独的强连通分量。

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

我认为这是正确的。但是，我找到了解决方案 here和 here假设 SCC 是 {C,J,F,H,I,G,D} 和 {A,E,B}。我的错误在哪里？

Answer 1

你的步骤是正确的，你的答案也是正确的，通过检查你提供的其他答案，你可以看到他们使用了不同的算法:首先你在 G 转置上运行 DFS，然后你在 G 上运行无向分量算法处理顶点按照上一步的帖子编号降序排列。

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