知识卡片
有向图无环当且仅当无返祖边
- DFS 若产生返祖边,祖先到当前点的树路径与该边合成环;
- 若原图有环,环上最先发现的顶点会把前驱纳入后代,产生返祖边。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第20章 基本图算法 · 查看原书依据
Lemma 20.11 A directed graph G is acyclic if and only if a depth-first search of G yields no back edges. Figure 20.7 (a) Professor Bumstead topologically sorts his clothing when getting dressed. Each directed edge (u, v) means that garment u
参考来源
- 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[50000,55000))。
- 结论依据:引理20.11给出双向条件,证明分别使用祖先路径和白路径定理。
- 原始内容:Lemma 20.11 A directed graph G is acyclic if and only if a depth-first search of G yields no back edges. Figure 20.7 (a) Professor Bumstead topologically sorts his clothing when getting dressed. Each directed edge ( u , v ) means that garment u