知识卡片

普通读书笔记卡 · 3650.a

DFS前驱形成森林

理解等级:中级

DFS 可能从多个未发现顶点重新开始,因此其父指针子图覆盖所有顶点,形成若干互不相交的深度优先树;每次以白色顶点为新根。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第20章 基本图算法 · 查看原书依据

      The predecessor subgraph of a depth-first search forms a depth-first forest comprising several depth-first trees. The edges in Eπ are tree edges. Like breadth-first search, depth-first search colors vertices during the search to indicate their state. Each vertex is initially white, is grayed when it is discovered in the search, and is blackened when it is finished, that is, when its adjacency list has been examined completely. This technique guarantees that each vertex ends up in exactly one depth-first tree, so that these trees are disjoint.

    参考来源

    - 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[30000,35000))。 - 结论依据:第20.3节以父指针定义前驱子图Gπ;多源重启使其成为若干树,每点由白变灰再变黑,保证仅入一棵树。 - 原始内容:The predecessor subgraph of a depth-first search forms a depth-first forest comprising several depth-first trees . The edges in E π are tree edges . Like breadth-first search, depth-first search colors vertices during the search to indicate their state. Each vertex is initially white, is grayed when it is discovered in the search, and is blackened when it is finished , that is, when its adjacency list has been examined completely. This technique guarantees that each vertex ends up in exactly one depth-first tree, so that these trees are disjoint.