知识卡片
DFS边分四类
- DFS 中,树边首次发现新顶点;
- 返祖边指向祖先且包括自环;
- 前向边是非树边但指向真后代;
- 其余跨向非祖先后代的边为横叉边。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · DFS边分四类
原书出处 · 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.