The Path-Based Approach to DFS
The path-based approach offers a
simple top-down development of the basic depth-first search graph
algorithms.
-
"Path-based depth-first search for strong and biconnected components,"
Information Processing Letters 74, 2000, pp.107-114.
-
"Searching",
book chapter
in
Handbook of Graph Theory, J.L. Gross and J. Yellen eds., pp.953-984,
2003.
-
Class notes
for a unit on dfs --
topological sort, strong components, bridges & cutpoints,
Robbins' Theorem for strongly connected orientation,
carving algorithm for smallest bridgeless subgraph
-
Homework problems
-
Powerpoint slides
for the strong components
algorithm
(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
-
Timing statistics
for the C code:
comparison of Path, LOWPOINT &
2-pass algorithms for strong components
-
History of the path-based algorithm
for strong components