知识卡片

普通读书笔记卡 · 3650.b

DFS发现和完成各记时间

理解等级:中级

每个顶点在首次发现与完成邻接表扫描时各获一个时间戳;2|V| 个事件产生 1 到 2|V| 的时间。

白、灰、黑分别对应未发现、活动中、已完成。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      Each vertex v has two timestamps: the first timestamp v.d records when v is first discovered (and grayed), and the second timestamp v.f records when the search finishes examining v’s adjacency list (and blackens v). These timestamps provide important information about the structure of the graph and are generally helpful in reasoning about the behavior of depth-first search. The procedure DFS on the facing page records when it discovers vertex u in the attribute u.d and when it finishes vertex u in the attribute u.f. These timestamps are integers between 1 and 2 |V|, since there is one discovery event and one finishing event for each of the |V| vertices. For every vertex u, Vertex u is WHITE before time u.d, GRAY between time u.d and time u.f, and BLACK thereafter.

    参考来源

    - 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[30000,35000))。 - 结论依据:第20.3节将v.d和v.f分别定义为发现与扫描完邻接表的时间,且每顶点各有一次事件;同段给出白灰黑时段。 - 原始内容:Each vertex v has two timestamps: the first timestamp v.d records when v is first discovered (and grayed), and the second timestamp v.f records when the search finishes examining v ’s adjacency list (and blackens v ). These timestamps provide important information about the structure of the graph and are generally helpful in reasoning about the behavior of depth-first search. The procedure DFS on the facing page records when it discovers vertex u in the attribute u.d and when it finishes vertex u in the attribute u.f . These timestamps are integers between 1 and 2 | V |, since there is one discovery event and one finishing event for each of the | V | vertices. For every vertex u , Vertex u is WHITE before time u.d , GRAY between time u.d and time u.f , and BLACK thereafter.