原书出处
Introduction to Algorithms, Fourth Edition
20 第20章 基本图算法
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