通过 DFS 查找图中的强连通分量

我正在阅读有关 BFS 和 DFS 的图算法。当我分析通过DFS在图中查找强连通分量的算法时，我想到了一个疑问。为了找到强连通分量，书（Coremen）做了什么，首先它在图上运行 DFS 以获得顶点的完成时间，然后再次以完成时间的降序在图的转置上运行 DFS这是我们从第一个 DFS 中得到的。但我无法理解为什么第二个 DFS 必须根据完成时间运行。 我的意思是，即使我们直接在图的转置上运行 DFS（忽略完成时间），它是否也可以为我们提供连接的组件，因为通过执行转置，我们已经阻塞了通往其他组件的路径。

编辑-以下是斯坦福大学关于该主题的一些精彩的深入视频：

http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms（参见 6. 有向图中的连接）

我的解释：

如果您不根据第一个 dfs 的完成时间递减来运行第二个 dfs，您可能会错误地将整个图识别为单个强连接组件 (SCC)。

请注意，在我的示例中，节点d从第一个 dfs 开始，完成时间总是最短的。节点之一a, b, or c将有最长的完成时间。让我们假设a具有最长的完成时间，因此如果我们根据递减的完成时间运行第二个 dfs，a会是第一。

现在，如果您从节点开始运行第二个 dfsd转置为G，您将生成包含整个图的深度优先森林，因此得出整个图是 SCC 的结论，这显然是错误的。但是，如果您使用以下命令启动 dfsa，那么你不仅会发现a, b, and c，作为一个 SCC，但重要的是他们将被标记为已访问颜色为灰色或黑色。然后当你继续 dfs 时d，你不会遍历它的 SCC，因为你会意识到它的相邻节点已被访问。

如果你查看 DFS 的 cormens 代码，

DFS(G)
1 for each vertex u in G.V
2     u.color = WHITE
3     u.π = NIL
4 time = 0
5 for each vertex u in G.V
6     if u.color == WHITE
7         DFS-VISIT(G, u)

DFS-VISIT(G, u)
1 time = time + 1 // white vertex u has just been discovered
2 u.d = time
3 u.color = GRAY
4 for each v in G.adj[u]
5     if v.color == WHITE
6         v.π = u
7         DFS-VISIT(G, u)
8 u.color = BLACK // blacken u; it is finished
9 time = time + 1
10 u.f = time

如果您不使用递减的完成时间，那么 DFS 的第 6 行只会为真一次，因为 DFS-VISIT 会递归地访问整个图。这会在深度优先森林中生成一棵树，每棵树都是一个 SCC。单棵树的原因是因为一棵树是由其前驱为零的根节点来标识的。