← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

20 第20章 基本图算法

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.720Z

t. Besides creating a depth-first forest, depth-first search also timestamps each vertex.

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.

In the DFS procedure, the input graph G may be undirected or directed. The variable time

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter020.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea