algorithm - 强连通分量算法背后的逻辑(正确性)(DFS的应用)

Question

“如果每个顶点都可以从其他每个顶点到达，则称有向图是强连通的”。

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 上阅读了一些答案，但没有给我适当的感觉。因此，请举例说明逻辑。提前致谢。

Answer 1

这里是算法的解释:-

1. 完成时间:- SCC 可以可视化为单个节点，我们可以从中形成图表。由 SCC 形成的图总是 DAG(有向无环图)，其中有一个源顶点和一个汇点顶点，就好像该图有一个循环，然后循环中的节点将组合成一个 SCC。形成源的 SCC 将只有出边，而汇只有入边。根据该逻辑，您可以推断出离源越近的 SCC 完成时间越长，而离汇越近的 SCC 完成时间越短。

2. 转置:当您对图进行转置时，源变为汇，汇变为源，但图的 SCC 保持不变，只是它们的循环被反转。

3. DFS:- 我们开始在具有较高完成时间的节点上计算 DFS，这些节点在 SCC 中更接近原始图中的源。首先，我们从 SCC 开始，它在原始版本中是源，但现在是汇。现在我们知道 sink 没有传出边，因此我们在其上评估 DFS 我们只访问属于该 SCC 的节点，因此当我们可以将它们分组为一个时。当第一个 SCC 被访问时，只有出边的 SCC 现在变成了新的汇，它在原始图中的完成时间第二高，所以现在我们可以做 DFS 来获取它的组件。

为了更清楚你可以搜索Kosaraju's SCC algorithm