我正在阅读有关 BFS 和 DFS 的图形算法。当我在分析通过 DFS 在图中找到强连通分量的算法时，我想到了一个疑问。为了找到强连接组件，书（Coremen）做了什么，首先它在图上运行 DFS 以获得顶点的完成时间，然后再次在图的转置上运行 DFS，以完成时间的递减顺序我们从第一个 DFS 得到的。但我无法理解为什么第二个 DFS 必须根据完成时间运行。我的意思是，即使我们直接在图的转置上运行 DFS（忽略完成时间），它是否也会给我们连接的组件，因为通过进行转置，我们已经阻止了到其他组件的路径。
问问题
15406 次
1 回答
16
编辑-这是斯坦福大学关于该主题的一些很好的深入视频：
http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms（参见 6. 有向图中的连接性）
我的解释：
如果您不根据第一个 dfs 的减少完成时间运行第二个 dfs，您可能会错误地将整个图识别为单个强连通分量 (SCC)。
请注意，在我的示例中，节点d始终具有从第一个 dfs 开始的最低完成时间。节点a、b或之一c将具有最长的完成时间。让我们假设a完成时间最长，因此如果我们根据减少的完成时间运行第二个 dfs，a将是第一个。
现在，如果您d在 的转置中以 node 开始运行第二个 dfs G，您将生成一个包含整个图的深度优先森林，因此得出整个图是 SCC 的结论，这显然是错误的。但是，如果您以 dfs 开头a，那么您不仅会发现a、b和c, 是一个 SCC，而且重要的部分是它们将被标记为已访问，并被涂成灰色或黑色。然后，当您继续 dfs on 时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。单棵树的原因是因为一棵树是由它的根节点标识的，它的根节点有一个 nil 前辈。
于 2012-12-07T19:15:49.290 回答