Depth First Traversal of a Graph

LA home
Computing
Algorithms
 glossary
 Graphs
  Directed
  DAG
  Undirected
  DF Trav
  Canonical
  Isomorphism
  Subg. Iso.
  Stable mrrg.
  DF Trav

The depth first traversal algorithm can be applied to both directed and undirected graphs. The following applies to directed graphs.

Choose some start vertex, v, and visit it. If there is a vertex, w, that is adjacent to v, i.e., there is an edge ⟨v, w⟩, and w has not been visited already, visit w. Repeat the above for w. If ever the current vertex has no unvisited vertices adjacent to it, fall back to the vertex prior to the current vertex and see if it has any more unvisited adjacent vertices.

The above process will visit every vertex if the graph is strongly connected, otherwise one or more unvisited vertices may remain. If so, pick one of them and continue the traversal from it.

The case of undirected graphs is similar.

—m
—output

-- L.A., May 2015.

The graph above is represented by the adjacency matrix m. The algorithm can easily be recast to operate on a different graph representation such as adjacency lists, say.

Applications of depth first traversal include topological sorting and critical path analysis of DAGs.

www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Tuesday, 19-Mar-2024 07:54:51 UTC.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.