← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3650.b.1.a

严格时间嵌套刻画后代

理解等级:中级

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 树祖先关系;等号不会发生,因为每次时间戳递增且每个事件唯一。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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 .