Let \(G\) be a graph. Given vertices \(v,v'\) of \(G\text{,}\) we might wish to find a path from \(v\) to \(v'\text{,}\) if one exists. We can do this by constructing a tree \(T \preceq G\text{.}\)
Algorithm16.4.1.Depth-first search.
To create a tree \(T\) that is a subgraph of a graph \(G\) wherein a path (in \(G\)) from \(v\) to \(v'\) is evident, begin with \(T\) containing the single vertex \(v\) and no edges. Set \(x=v\text{.}\)
Look for a vertex \(y\) of \(G\) which is adjacent to \(x\) but not already in \(T\text{.}\) If such a \(y\) is found, go to Step 2. Otherwise, go to Step 3.
Adjoin \(y\) and a single edge between \(x\) and \(y\) to \(T\text{.}\) If \(y = v'\text{,}\) stop — a path from \(v\) to \(v'\) exists and is now contained in \(T\text{.}\) Otherwise, set \(x=y\) and return to Step 1.
If you have arrived here immediately after beginning the algorithm (i.e. with \(x\) still set to be \(v\)), stop — there is no path from \(v\) to \(v'\text{.}\) Otherwise, return to the vertex \(z\) adjoined before \(x\text{.}\) Set \(x = z\) and return to Step 1.
Note16.4.2.
In Step 1 of the algorithm, there is no specification on how to choose a single \(y\) satisfying the search criteria from multiple possibilities. In other words, there is flexibility in the implementation of the algorithm here, and for the problem at hand there may be implementation choices that are more expedient then others.
Example16.4.3.Carrying out a depth-first search.
We perform a Depth-first search on the graph in Figure 16.4.4, attempting to find a path from vertex \(1\) to vertex \(9\text{.}\) In carrying out the algorithm, if we always choose the vertex with the smallest label in Step 1, we obtain the graph in Figure 16.4.(a). The graph in Figure 16.4.(b) is the result of always choosing the vertex with the largest label.
Figure16.4.4.An example graph to illustrate depth-first search.
(a)Result of always choosing to move to the next adjacent vertex of smallest index.
(b)Result of always choosing to move to the next adjacent vertex of largest index.
Figure16.4.5.Results of two different implementation choices in a depth-first search.
The depth-first search will not necessarily yield the shortest path from \(v\) to \(v'\text{.}\) The following algorithm will.
Algorithm16.4.6.Breadth-first search.
To create a tree \(T\) that is a subgraph of a graph \(G\) wherein the shortest path in \(G\) from \(v\) to \(v'\) is evident, begin with \(T\) containing the single vertex \(v\) and no edges.
For each vertex \(x\) in \(T\) added in the last application of this step (or, in the case of the first application of this step, for \(x = v\)), adjoin all vertices of \(G\) that are adjacent to \(x\) and not already in \(T\text{,}\) along with a single edge between each such vertex and \(x\text{.}\) If at least one vertex has been adjoined to \(T\) in this step, proceed to Step 2. Otherwise, stop — there is no path from \(v\) to \(v'\) in \(G\text{.}\)
If \(v'\) was one of the vertices adjoined in Step 1, stop — a path from \(v\) to \(v'\) exists and is now contained in \(T\text{.}\) Otherwise, return to Step 1.
Example16.4.7.Carrying out a breadth-first search.
Below is the result of the breadth-first algorithm, carried out to find a path from \(1\) to \(9\) in the graph in Figure 16.4.4 from Example 16.4.3.
Figure16.4.8.The result of a breadth-first search.
