“如果每个顶点都可以从其他每个顶点到达,则称有向图是强连通的”。
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 步 背后的逻辑,但没有理解。请帮助我理解这一点,给我背后的感觉。
我在 SO 上阅读了一些答案,但没有给我适当的感觉。因此,请举例说明逻辑。提前致谢。
最佳答案
这里是算法的解释:-
完成时间:- SCC 可以可视化为单个节点,我们可以从中形成图表。由 SCC 形成的图总是 DAG(有向无环图),其中有一个源顶点和一个汇点顶点,就好像该图有一个循环,然后循环中的节点将组合成一个 SCC。形成源的 SCC 将只有出边,而汇只有入边。根据该逻辑,您可以推断出离源越近的 SCC 完成时间越长,而离汇越近的 SCC 完成时间越短。
转置:当您对图进行转置时,源变为汇,汇变为源,但图的 SCC 保持不变,只是它们的循环被反转。
DFS:- 我们开始在具有较高完成时间的节点上计算 DFS,这些节点在 SCC 中更接近原始图中的源。首先,我们从 SCC 开始,它在原始版本中是源,但现在是汇。现在我们知道 sink 没有传出边,因此我们在其上评估 DFS 我们只访问属于该 SCC 的节点,因此当我们可以将它们分组为一个时。当第一个 SCC 被访问时,只有出边的 SCC 现在变成了新的汇,它在原始图中的完成时间第二高,所以现在我们可以做 DFS 来获取它的组件。
为了更清楚你可以搜索Kosaraju's SCC algorithm
关于algorithm - 强连通分量算法背后的逻辑(正确性)(DFS的应用),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20835804/