← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3650.a.3

DFS边分四类

理解等级:中级
  • DFS 中,树边首次发现新顶点;
  • 返祖边指向祖先且包括自环;
  • 前向边是非树边但指向真后代;
  • 其余跨向非祖先后代的边为横叉边。
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The depth-first forest Gπ produced by a depth-first search on graph G can contain four types of edges: Tree edges are edges in the depth-first forest Gπ. Edge (u, v) is a tree edge if v was first discovered by exploring edge (u, v). Back edges are those edges (u, v) connecting a vertex u to an ancestor v in a depth-first tree. We consider self-loops, which may occur in directed graphs, to be back edges. Forward edges are those nontree edges (u, v) connecting a vertex u to a proper descendant v in a depth-first tree. Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.

    参考来源

    - 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[40000,45000))。 - 结论依据:第20.3节按DFS森林中的父子、祖先、真后代及其他位置定义树边、返祖边、前向边、横叉边;自环按返祖边处理。 - 原始内容:The depth-first forest G π produced by a depth-first search on graph G can contain four types of edges: Tree edges are edges in the depth-first forest G π . Edge ( u , v ) is a tree edge if v was first discovered by exploring edge ( u , v ). Back edges are those edges ( u , v ) connecting a vertex u to an ancestor v in a depth-first tree. We consider self-loops, which may occur in directed graphs, to be back edges. Forward edges are those nontree edges ( u , v ) connecting a vertex u to a proper descendant v in a depth-first tree. Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.