如何在图表中找到强连通组件？

Question

我正在尝试自学图论,现在试图了解如何在图中找到SCC.我已在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]的顺序考虑顶点(在步骤1中计算)
4. 输出步骤3的深度优先林中每棵树的顶点作为单独的强连接组件

观察下面的图表(问题是3.4从这里开始.我在这里和这里找到了几个解决方案,但我试图打破这个并自己理解它.)

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

从顶点A开始运行DFS:

请注意格式为[Pre-Vist,Post-visit]的RED文本

第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}

这是我认为是正确的.但是,我在这里和这里发现的解决方案是SCC是{C,J,F,H,I,G,D}和{A,E,B}.我的错误在哪里？

Answer 1

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

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