强连通组件算法背后的逻辑(正确性)(DFS的应用)
强连通组件算法背后的逻辑(正确性)(DFS的应用)
提问于 2013-12-30 08:17:42
所谓有向图是强连通的，如果每个顶点都可以从其他顶点到达的话。
Coreman给出的算法如下：
STRONGLY-CONNECTED-COMPONENTS (G)
1. Call DFS(G) to compute finishing times f[u] for all u.
2. Compute GT
3. Call DFS(GT), but in the main loop, consider vertices in order of decreasing f[u] (as computed in first DFS)
4. Output the vertices in each tree of the depth-first forest formed in second DFS as a separate SCC.我试图理解这个算法的正确性，以及步骤3背后的逻辑，但没有理解。请帮助我理解这个，给我这个背后的感觉。
我读了一些答案，但没有给我适当的感觉。所以请用逻辑来解释，例如。提前谢谢。
Stack Overflow用户
回答已采纳
发布于 2013-12-30 09:19:46
以下是算法的说明:-
- 完成时间 :- SCC's可以可视化单个节点，我们可以从它们生成一个图形。由SCC形成的图总是DAG(有向无圈图)，其中有一个源顶点和一个汇顶点，就好像该图有一个循环，那么循环中的节点将合并成一个SCC。形成源的SCC只具有传出的边缘，而接收器只有传入的边缘。根据这种逻辑，您可以推断离源更近的SCC将有更高的完成时间，而靠近接收器的SCC将有更低的完成时间。
- 转置：-当你接受图形的转置时，源变成汇，汇变成源，但是图的SCC保持不变，但它们的循环是相反的。
- DFS :-我们开始在完成时间较高的节点上计算DFS，这些节点在SCC中更接近原始图中的源。首先，我们从SCC开始，它是原始源，但现在它是水槽。现在我们知道接收器没有传出的边缘，因此我们在它上评估DFS，我们只访问作为SCC一部分的节点，因此当我们可以将它们分组为一个。当第一次访问SCC时，只有向外的边缘的SCC现在成为了新的接收器，在原始图中有第二高的完成时间，所以现在我们可以做DFS来获得它的组件。
为了更清晰起见，您可以搜索Kosaraju的SCC算法
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20835804
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号