原书出处
Introduction to Algorithms, Fourth Edition
20 第20章 基本图算法
n. The DFS algorithm has enough information to classify some edges as it encounters them.
The key idea is that when an edge (u, v) is first explored, the color of vertex v says something about the edge: WHITE indicates a tree edge, GRAY indicates a back edge, and BLACK indicates a forward or cross edge. The first case is immediate from the specification of the algorithm. For the second case, observe that the gray vertices always form a linear chain of descendants corresponding to the stack of active DFS-VISIT invocations.
The number of gray vertices is 1 more than the depth in the depth-first forest of the ver
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter020.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea