Depth-first search

DFS

A method of searching a finite directed or undirected graph $G=(V,E)$ along the edges of the graph and numbering its vertices. Depth-first search on undirected connected graphs works recursively, starting with an arbitrary vertex with DFS number $1$ and, having numbered $k$ vertices already, an unnumbered neighbour $w$ of vertex $v$ with number $k$ will obtain number $k+1$ and defines a tree edge from $w$ to $v$ until all vertices are numbered. At the end the set of these tree edges represents a spanning tree of $G$. When depth-first search reaches a vertex $v$ all of whose neighbours are already numbered and $v$ has a DFS number larger than $1$, then depth-first search backtracks one step to the predecessor $w$ of $v$ along the corresponding tree edge and tries to find a next unnumbered neighbour of $w$. If the graph is not connected (cf. Graph, connectivity of a), then the procedure starts again on every connected component of the graph. For directed graphs the procedure is more complicated but similar.

For the special case of binary trees this numbering is known as pre-order, a vertex ordering which plays an important role in computer science.

Depth-first search can be implemented in linear time $O(|V|+|E|)$ by using a representation of the graph as linked adjacency lists. Basing on depth-first search one can determine the $2$-connected components of an undirected graph as well as the strongly connected components of a directed graph in linear time (cf. [a1]). There are other, deep applications of depth-first search; for example, planarity of graphs (cf. Graph, planar) can be recognized in linear time using depth-first search [a6].

References

[a1]	A.V. Aho, J.E. Hopcroft, J.D. Ullman, "The design and analysis of computer algorithms" , Addison-Wesley (1976)
[a2]	S. Even, "Graph algorithms" , Computer Sci. Press (1979)
[a3]	K. Mehlhorn, "Graph algorithms and NP-completeness" , Data structures and algorithms , 2 , Springer (1984)
[a4]	T.H. Cormen, C.E. Leiserson, R.L. Rivest, "Introduction to algorithms" , MIT & McGraw-Hill (1990)
[a5]	J.E. Hopcroft, R.E. Tarjan, "Efficient algorithms for graph manipulation" Comm. ACM , 16 (1973) pp. 372–378
[a6]	J.E. Hopcroft, R.E. Tarjan, "Efficient planarity testing" J. ACM , 21 (1974) pp. 549–568