如何在图中找到强连通分量？
How to find Strongly Connected Components in a Graph?
我正在尝试自学图论，现在正试图了解如何找到 SCC in a graph. I have read several different questions/answers on SO (e.g., 1,2,3,4,5,6,7,8)，但我无法找到一个包含我可以遵循的完整分步示例的示例。
根据CORMEN (Introduction to Algorithms)，一种方法是：
- Call DFS(G) to compute finishing times f[u] for each vertex u
- Compute Transpose(G)
- 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)
- Output the vertices of each tree in the depth-first forest of step 3 as a separate strong connected component
观察下图（问题是 here. I have found several solutions here and here 的 3.4，但我试图自己分解并理解它。）
第 1 步：调用 DFS(G) 计算每个顶点 u
的完成时间 f[u]
运行 DFS 从顶点 A 开始：
请注意红色文本格式为 [Pre-Vist, Post-Visit]
步骤 2：计算转置 (G)
步骤 3. 调用 DFS(Transpose(G))，但在 DFS 的主循环中，按照 f[u] 递减的顺序考虑顶点（如步骤 1 中计算的那样）
好的，所以顶点按 post-访问（完成时间）值递减的顺序排列：
{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}
我认为这是正确的。但是，我发现 here and here 的解决方案说 SCC 是 {C,J,F,H,I,G,D} 和 {A,E,B}。我的错误在哪里？
你的步骤是正确的，你的答案也是正确的，通过检查你提供的其他答案，你可以看到他们使用了不同的算法：首先你运行 DFS on G t运行sposed然后你 运行 G 上的一个无向分量算法按照上一步的 post 编号的降序处理顶点。
问题是他们 运行 G t运行sposed 而不是 G 中的最后一步，因此得到了不正确的答案。如果你从第 98 页开始阅读 Dasgupta，你会看到他们（尝试）使用的算法的详细解释。
你的回答是正确的。根据 CLRS，"A strongly connected component of a directed graph G = (V,E) is a maximal set of vertices C, such that for every pair of vertices u and v, we have both u ~> v and v ~> u, i.e. vertices v and u are reachable from each other."
如果你假设 {C, J, F, H, I, G, D} 是正确的，那么就没有办法从 D 到 G（还有许多其他谬误），和其他集合一样，无法从 A 到达 E。
我正在尝试自学图论，现在正试图了解如何找到 SCC in a graph. I have read several different questions/answers on SO (e.g., 1,2,3,4,5,6,7,8)，但我无法找到一个包含我可以遵循的完整分步示例的示例。
根据CORMEN (Introduction to Algorithms)，一种方法是：
- Call DFS(G) to compute finishing times f[u] for each vertex u
- Compute Transpose(G)
- 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)
- Output the vertices of each tree in the depth-first forest of step 3 as a separate strong connected component
观察下图（问题是 here. I have found several solutions here and here 的 3.4，但我试图自己分解并理解它。）
第 1 步：调用 DFS(G) 计算每个顶点 u
的完成时间 f[u]运行 DFS 从顶点 A 开始：
请注意红色文本格式为 [Pre-Vist, Post-Visit]
步骤 2：计算转置 (G)
步骤 3. 调用 DFS(Transpose(G))，但在 DFS 的主循环中，按照 f[u] 递减的顺序考虑顶点（如步骤 1 中计算的那样）
好的，所以顶点按 post-访问（完成时间）值递减的顺序排列：
{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}
我认为这是正确的。但是，我发现 here and here 的解决方案说 SCC 是 {C,J,F,H,I,G,D} 和 {A,E,B}。我的错误在哪里？
你的步骤是正确的，你的答案也是正确的，通过检查你提供的其他答案，你可以看到他们使用了不同的算法：首先你运行 DFS on G t运行sposed然后你 运行 G 上的一个无向分量算法按照上一步的 post 编号的降序处理顶点。
问题是他们 运行 G t运行sposed 而不是 G 中的最后一步，因此得到了不正确的答案。如果你从第 98 页开始阅读 Dasgupta，你会看到他们（尝试）使用的算法的详细解释。
你的回答是正确的。根据 CLRS，"A strongly connected component of a directed graph G = (V,E) is a maximal set of vertices C, such that for every pair of vertices u and v, we have both u ~> v and v ~> u, i.e. vertices v and u are reachable from each other."
如果你假设 {C, J, F, H, I, G, D} 是正确的，那么就没有办法从 D 到 G（还有许多其他谬误），和其他集合一样，无法从 A 到达 E。