Path-based dfs
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
-
finding strong and biconnected components
-
orienting an undirected (or mixed) graph to make it
strongly connected
-
finding an odd directed cycle
-
checking uniqueness of perfect matchings
-
finding a Hamiltonian path in a tournament
These applications and others are discussed on these web pages.
The
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
corresponding disadvantage
is that more intricate problems (for instance planarity testing) require
the full power of the dfs tree.
Path-based dfs
is a natural concept, dating from 19th century work
on threading mazes (Tremaux's algorithm and others).