知识卡片
严格时间嵌套刻画后代
DFS 首次发现顶点 u 时记录 u.d,扫描完它的全部后代并返回时记录 u.f,因此 [u.d,u.f] 是 u 处于活动递归栈中的时间区间。
顶点 v 是 u 的真后代,当且仅当 u.d<v.d<v.f<u.f:搜索在 u 尚未完成时进入 v,又必须先完成 v 才能完成 u。所以可用时间戳区间的严格包含关系判断 DFS 树祖先关系;等号不会发生,因为每次时间戳递增且每个事件唯一。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第20章 基本图算法 · 查看原书依据
Corollary 20.8 (Nesting of descendants’ intervals) Vertex v is a proper descendant of vertex u in the depth-first forest for a (directed or undirected) graph G if and only if u.d < v.d < v.f < u.f.
参考来源
- 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[40000,45000))。
- 结论依据:推论20.8直接给出v为u真后代当且仅当u.d<v.d<v.f<u.f;前提是有向或无向图的一次DFS森林。
- 原始内容:Corollary 20.8 (Nesting of descendants’ intervals) Vertex v is a proper descendant of vertex u in the depth-first forest for a (directed or undirected) graph G if and only if u.d < v.d < v.f < u.f .