The Path-Based Approach to DFS
The path-based approach offers a
simple top-down development of the basic depth-first search graph
"Path-based depth-first search for strong and biconnected components,"
Information Processing Letters 74, 2000, pp.107-114.
Handbook of Graph Theory, J.L. Gross and J. Yellen eds., pp.953-984,
for a unit on dfs --
topological sort, strong components, bridges & cutpoints,
Robbins' Theorem for strongly connected orientation,
carving algorithm for smallest bridgeless subgraph
for the strong components
(on opening, click "Cancel" on the menu about "links")
- C code for strong components algorithms (path-based, LOWPOINT, and 2-pass)
with graph generators and timers, by San Skulrattanakulchai.
list of the routines
- tarfile of the routines
for the C code:
comparison of Path, LOWPOINT &
2-pass algorithms for strong components
History of the path-based algorithm
for strong components