知识卡片
分量图按拓扑次序被访问
转置图上的第二次DFS按转置分量图的逆拓扑序访问。
将该分量图边反向,原文指出得到原图分量图,因此在原图分量图中按拓扑序访问;所用分量图恒等式的证明仍是习题20.5-4的任务。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第20章 基本图算法 · 查看原书依据
If you reverse the edges of (GT)SCC, you get the graph ((GT)SCC)T. Because ((GT)SCC)T = GSCC (see Exercise 20.5-4), the second depth-first search visits the vertices of GSCC in topologically sorted order.
参考来源
- 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[65000,70000))。
- 结论依据:第20.5节先给转置分量图逆拓扑访问,再由反转边及分量图恒等式推出原图拓扑序;恒等式的证明留给习题20.5-4。
- 原始内容:If you reverse the edges of ( G T ) SCC , you get the graph (( G T ) SCC ) T . Because (( G T ) SCC ) T = G SCC (see Exercise 20.5-4), the second depth-first search visits the vertices of G SCC in topologically sorted order.