知识卡片

普通读书笔记卡 · 3651.a.1

有向图无环当且仅当无返祖边

理解等级:中级
  • 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