Depth-First Search

 
Figure: An undirected graph and its depth-first search tree  

Depth-first search turns out to be, in general, even more useful than breadth-first search. The reason is that a depth-first search of a graph organizes the edges of the graph in a very precise way, which is quite different from breadth-first search. As with BFS, we assign a direction to each edge when we discover it, as shown in Figure .  

 
Figure: Edge possibilities for search trees  

Although there are four conceivable classes of edges resulting from such labelings, as shown in Figure , only two of them can occur with undirected graphs. In a DFS of an undirected graph, every edge is either in the tree or goes directly back to an ancestor. Why? Suppose we encountered a forward edge (x,y) directed toward a decendant vertex. In this case, we would have discovered (x,y) when exploring y, making it a back edge. Suppose we encounter a cross edge (x,y), linking two unrelated vertices. Again, we would have discovered this edge when we explored y, making it a tree edge. For directed graphs, depth-first search labelings can take on a wider range of possibilities.

Depth-first search has a neat recursive implementation, which eliminates the need to explicitly use a stack:

DFS(G,u)

		 state[u] = ``discovered''

		 process vertex u if desired

		for each    do

				 process edge (u,v) if desired

				 if state[v] = ``undiscovered'' then

				 		 p[v] = u

				 		 DFS(G,v)

		state[u] = ``completely-explored''

As with BFS, this implementation of the depth-first search algorithm includes places to optionally process each vertex and edge, say to copy them, print them, or count them. Both algorithms will traverse all edges in the same connected component as the starting point. Since we need to start with a vertex in each component in order to traverse a disconnected graph, we must start from any vertex remaining undiscovered after a component search. With the proper initialization, this completes the traversal algorithm:

DFS-graph(G)

		for each vertex    do

				 state[u] = ``undiscovered''

		for each vertex    do

				 if state[u] = ``undiscovered'' then

							initialize new component, if desired

							DFS[G,u]