views depth-first search as maintaining a path, rather than
building a depth-first spanning tree.
This leads to simplified
algorithms for problems such as
These applications and others are discussed on these web pages.
finding strong and biconnected components
orienting an undirected (or mixed) graph to make it
finding an odd directed cycle
checking uniqueness of perfect matchings
finding a Hamiltonian path in a tournament
advantage of path-based dfs is simplicity -- the dfs path captures
the structure of many problems, without need for the more complicated
dfs tree. A
is that more intricate problems (for instance planarity testing) require
the full power of the dfs tree.
is a natural concept, dating from 19th century work
on threading mazes (Tremaux's algorithm and others).