知识卡片
两次DFS求强连通分量
强连通分量是极大的顶点集合,其中任意两点都能互相到达。图的转置 Gᵀ 把每条边 (u,v) 反向为 (v,u);DFS 的完成时间 u.f 是 u 的所有可继续探索后代都处理完、搜索从 u 返回的时刻。
- 先在 G 上 DFS 记录完成时间,
- 再建转置图
Gᵀ; - 按第一遍所得完成时间递减的顺序,在
Gᵀ上启动第二次 DFS。
转置不会改变哪些顶点互相可达,却会反转分量之间的边;第一遍完成时间的顺序保证第二遍不会从当前分量越入尚未输出的分量。因此第二次 DFS 森林的每棵树恰好对应一个强连通分量,整体耗时 Θ(V+E)。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第20章 基本图算法 · 查看原书依据
STRONGLY-CONNECTED-COMPONENTS(G) 1 call DFS(G) to compute finish times u.f for each vertex u 2 create GT 3 call DFS(GT), but in the main loop of DFS, consider the vertices in order of decreasing u.f (as computed in line 1) 4 output the vertices of each tree in the depth-first forest formed in line 3 as a separate strongly connected component
参考来源
- 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[55000,60000))。
- 结论依据:第20.5节四步伪代码依次给出原图DFS完成时间、建转置图、按完成时间递减二次DFS及每棵树输出为一分量;前段给建转置和总时间Θ(V+E)。
- 原始内容:S TRONGLY -C ONNECTED -C OMPONENTS ( G ) 1 call DFS( G ) to compute finish times u.f for each vertex u 2 create G T 3 call DFS( G T ), but in the main loop of DFS, consider the vertices in order of decreasing u.f (as computed in line 1) 4 output the vertices of each tree in the depth-first forest formed in line 3 as a separate strongly connected component