原书出处
Introduction to Algorithms, Fourth Edition
20 第20章 基本图算法
ch the predecessor subgraph is Gπ = (V, Eπ), where Eπ = {(v.π, v) : v ∈ V and v.π ≠ NIL}.
The predecessor subgraph of a depth-first search forms a depth-first forest comprising several depth-first trees. The edges in Eπ are tree edges. Like breadth-first search, depth-first search colors vertices during the search to indicate their state. Each vertex is initially white, is grayed when it is discovered in the search, and is blackened when it is finished, that is, when its adjacency list has been examined completely. This technique guarantees that each vertex ends up in exactly one depth-first tree, so that these trees are disjoint.
Besides creating a depth-first forest, depth-first search also timestamps each vertex. Ea
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter020.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea