通过DFS在图形中查找强连接组件

Question

我正在阅读关于BFS和DFS的图算法.当我分析通过DFS在Graph中查找强连通分量的算法时,我想到了一个疑问.为了找到强连通分量,什么书(Coremen)做,首先它在图上运行DFS以获得顶点的结束时间然后再次按照完成时间的降序在图的转置上运行DFS我们从第一个DFS得到的.但是我无法理解为什么第二个DFS必须按照完成时间运行.我的意思是即使我们直接在图的转置上运行DFS(忽略完成时间),它是否也给了我们连接的组件,因为通过转置我们已经阻止了到其他组件的路径.

Answer 1

编辑 - 这是斯坦福大学关于这个主题的一些很好的深入视频:

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时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.单个树的推理是因为树的根节点具有零前导码.