我实在无法理解的强连通分量算法的工作 [英] I can not really understand how the strongly connected component algorithm works

问题描述

这是我的书的强连通分量的算法：

The strongly connected component algorithm from my book:

强连接组件（G）

1. 在调用DFS（G）来计算完成时间F [U]每个顶点u
2. 在计算转置（G）
3. 在调用DFS（移调（G）），但在DFS的主循环，考虑到顶点，以降低F的[U]（如计算在第1行）
4. 输出在步骤3的深度优先森林每棵树的顶点作为一个独立强大的连接组件

我真的不明白怎么行4件作品，算法如何使从DFS的转置图表森林。我不明白为什么要两次打电话给DFS。

I do not really understand how line 4 works, how the algorithm makes the forest from the DFS on the transpose graph. I do understand why to call both times to DFS.

感谢您的帮助。

推荐答案

在DFS主循环呼吁每个顶点探索从顶点到达的顶点递归辅助函数。 树这里是一组顶点的新的访问通过这些递归调用之一。辅助函数必须进行修改，以建立这一套，这是一个强大的组件时，它不为空。

The DFS main loop calls a recursive helper function on each vertex to explore the vertices reachable from that vertex. A "tree" here is the set of vertices newly visited by one of these recursive calls. The helper function must be modified to construct this set, which is a strong component whenever it is nonempty.

这篇关于我实在无法理解的强连通分量算法的工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！