12.3 Graph Traversal

In this section we present two algorithms for exploring a graph, starting at one of its vertices, $\ensuremath{\ensuremath{\mathit{i}}}$, and finding all vertices that are reachable from $\ensuremath{\ensuremath{\mathit{i}}}$. Both of these algorithms are best suited to graphs represented using an adjacency list representation. Therefore, when analyzing these algorithms we will assume that the underlying representation is an AdjacencyLists.

12.3.1 Breadth-First Search

The bread-first-search algorithm starts at a vertex $\ensuremath{\ensuremath{\mathit{i}}}$ and visits, first the neighbours of $\ensuremath{\ensuremath{\mathit{i}}}$, then the neighbours of the neighbours of $\ensuremath{\ensuremath{\mathit{i}}}$, then the neighbours of the neighbours of the neighbours of $\ensuremath{\ensuremath{\mathit{i}}}$, and so on.

This algorithm is a generalization of the breadth-first traversal algorithm for binary trees (Section 6.1.2), and is very similar; it uses a queue, $\ensuremath{\ensuremath{\mathit{q}}}$, that initially contains only $\ensuremath{\ensuremath{\mathit{i}}}$. It then repeatedly extracts an element from $\ensuremath{\ensuremath{\mathit{q}}}$ and adds its neighbours to $\ensuremath{\ensuremath{\mathit{q}}}$, provided that these neighbours have never been in $\ensuremath{\ensuremath{\mathit{q}}}$ before. The only major difference between the breadth-first-search algorithm for graphs and the one for trees is that the algorithm for graphs has to ensure that it does not add the same vertex to $\ensuremath{\ensuremath{\mathit{q}}}$ more than once. It does this by using an auxiliary boolean array, $\ensuremath{\ensuremath{\mathit{seen}}}$, that tracks which vertices have already been discovered.

An example of running $\ensuremath{\mathrm{bfs}(\ensuremath{\mathit{g}},0)}$ on the graph from Figure 12.1 is shown in Figure 12.4. Different executions are possible, depending on the ordering of the adjacency lists; Figure 12.4 uses the adjacency lists in Figure 12.3.

Figure 12.4: An example of bread-first-search starting at node 0. Nodes are labelled with the order in which they are added to $\ensuremath{\ensuremath{\mathit{q}}}$. Edges that result in nodes being added to $\ensuremath{\ensuremath{\mathit{q}}}$ are drawn in black, other edges are drawn in grey.

Analyzing the running-time of the $\ensuremath{\mathrm{bfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{i}})}$ routine is fairly straightforward. The use of the $\ensuremath{\ensuremath{\mathit{seen}}}$ array ensures that no vertex is added to $\ensuremath{\ensuremath{\mathit{q}}}$ more than once. Adding (and later removing) each vertex from $\ensuremath{\ensuremath{\mathit{q}}}$ takes constant time per vertex for a total of $O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}})$ time. Since each vertex is processed by the inner loop at most once, each adjacency list is processed at most once, so each edge of $G$ is processed at most once. This processing, which is done in the inner loop takes constant time per iteration, for a total of $O(\ensuremath{\ensuremath{\ensuremath{\mathit{m}}}})$ time. Therefore, the entire algorithm runs in $O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}+\ensuremath{\ensuremath{\ensuremath{\mathit{m}}}})$ time.

The following theorem summarizes the performance of the $\ensuremath{\mathrm{bfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ algorithm.

Theorem 12..3   When given as input a Graph, $\ensuremath{\ensuremath{\mathit{g}}}$, that is implemented using the AdjacencyLists data structure, the $\ensuremath{\mathrm{bfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ algorithm runs in $O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}+\ensuremath{\ensuremath{\ensuremath{\mathit{m}}}})$ time.

A breadth-first traversal has some very special properties. Calling $\ensuremath{\mathrm{bfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ will eventually enqueue (and eventually dequeue) every vertex $\ensuremath{\ensuremath{\mathit{j}}}$ such that there is a directed path from $\ensuremath{\ensuremath{\mathit{r}}}$ to $\ensuremath{\ensuremath{\mathit{j}}}$. Moreover, the vertices at distance 0 from $\ensuremath{\ensuremath{\mathit{r}}}$ ( $\ensuremath{\ensuremath{\mathit{r}}}$ itself) will enter $\ensuremath{\ensuremath{\mathit{q}}}$ before the vertices at distance 1, which will enter $\ensuremath{\ensuremath{\mathit{q}}}$ before the vertices at distance 2, and so on. Thus, the $\ensuremath{\mathrm{bfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ method visits vertices in increasing order of distance from $\ensuremath{\ensuremath{\mathit{r}}}$ and vertices that cannot be reached from $\ensuremath{\ensuremath{\mathit{r}}}$ are never visited at all.

A particularly useful application of the breadth-first-search algorithm is, therefore, in computing shortest paths. To compute the shortest path from $\ensuremath{\ensuremath{\mathit{r}}}$ to every other vertex, we use a variant of $\ensuremath{\mathrm{bfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ that uses an auxilliary array, $\ensuremath{\ensuremath{\mathit{p}}}$, of length $\ensuremath{\ensuremath{\mathit{n}}}$. When a new vertex $\ensuremath{\ensuremath{\mathit{j}}}$ is added to $\ensuremath{\ensuremath{\mathit{q}}}$, we set $\ensuremath{\ensuremath{\mathit{p}}[\ensuremath{j}]\gets \ensuremath{i}}$. In this way, $\ensuremath{\ensuremath{\mathit{p}}[\ensuremath{\mathit{j}}]}$ becomes the second last node on a shortest path from $\ensuremath{\ensuremath{\mathit{r}}}$ to $\ensuremath{\ensuremath{\mathit{j}}}$. Repeating this, by taking $\ensuremath{\ensuremath{\mathit{p}}[\ensuremath{\mathit{p}}[\ensuremath{\mathit{j}}]}$, $\ensuremath{\ensuremath{\mathit{p}}[\ensuremath{\mathit{p}}[\ensuremath{\mathit{p}}[\ensuremath{\mathit{j}}]}]]$, and so on we can reconstruct the (reversal of) a shortest path from $\ensuremath{\ensuremath{\mathit{r}}}$ to $\ensuremath{\ensuremath{\mathit{j}}}$.

12.3.2 Depth-First Search

The depth-first-search algorithm is similar to the standard algorithm for traversing binary trees; it first fully explores one subtree before returning to the current node and then exploring the other subtree. Another way to think of depth-first-search is by saying that it is similar to breadth-first search except that it uses a stack instead of a queue.

During the execution of the depth-first-search algorithm, each vertex, $\ensuremath{\ensuremath{\mathit{i}}}$, is assigned a colour, $\ensuremath{\ensuremath{\mathit{c}}[\ensuremath{\mathit{i}}]}$: $\ensuremath{\ensuremath{\mathit{white}}}$ if we have never seen the vertex before, $\ensuremath{\ensuremath{\mathit{grey}}}$ if we are currently visiting that vertex, and $\ensuremath{\ensuremath{\mathit{black}}}$ if we are done visiting that vertex. The easiest way to think of depth-first-search is as a recursive algorithm. It starts by visiting $\ensuremath{\ensuremath{\mathit{r}}}$. When visiting a vertex $\ensuremath{\ensuremath{\mathit{i}}}$, we first mark $\ensuremath{\ensuremath{\mathit{i}}}$ as $\ensuremath{\ensuremath{\mathit{grey}}}$. Next, we scan $\ensuremath{\ensuremath{\mathit{i}}}$'s adjacency list and recursively visit any white vertex we find in this list. Finally, we are done processing $\ensuremath{\ensuremath{\mathit{i}}}$, so we colour $\ensuremath{\ensuremath{\mathit{i}}}$ black and return.

An example of the execution of this algorithm is shown in Figure 12.5.

Figure 12.5: An example of depth-first-search starting at node 0. Nodes are labelled with the order in which they are processed. Edges that result in a recursive call are drawn in black, other edges are drawn in $\ensuremath{\ensuremath{\mathit{grey}}}$.

Although depth-first-search may best be thought of as a recursive algorithm, recursion is not the best way to implement it. Indeed, the code given above will fail for many large graphs by causing a stack overflow. An alternative implementation is to replace the recursion stack with an explicit stack, $\ensuremath{\ensuremath{\mathit{s}}}$. The following implementation does just that:

In the preceding code, when the next vertex, $\ensuremath{\ensuremath{\mathit{i}}}$, is processed, $\ensuremath{\ensuremath{\mathit{i}}}$ is coloured $\ensuremath{\ensuremath{\mathit{grey}}}$ and then replaced, on the stack, with its adjacent vertices. During the next iteration, one of these vertices will be visited.

Not surprisingly, the running times of $\ensuremath{\mathrm{dfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ and $\ensuremath{\mathrm{dfs2}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ are the same as that of $\ensuremath{\mathrm{bfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$:

Theorem 12..4   When given as input a Graph, $\ensuremath{\ensuremath{\mathit{g}}}$, that is implemented using the AdjacencyLists data structure, the $\ensuremath{\mathrm{dfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ and $\ensuremath{\mathrm{dfs2}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ algorithms each run in $O(\ensuremath{\ensuremath{\ensuremath{\mathit{n}}}}+\ensuremath{\ensuremath{\ensuremath{\mathit{m}}}})$ time.

As with the breadth-first-search algorithm, there is an underlying tree associated with each execution of depth-first-search. When a node $\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}\neq \ensuremath{\ensuremath{\ensuremath{\mathit{r}}}}$ goes from $\ensuremath{\ensuremath{\mathit{white}}}$ to $\ensuremath{\ensuremath{\mathit{grey}}}$, this is because $\ensuremath{\mathrm{dfs}(\ensuremath{\mathit{g}},\ensuremath{\mathit{i}},\ensuremath{\mathit{c}})}$ was called recursively while processing some node $\ensuremath{i}'$. (In the case of $\ensuremath{\mathrm{dfs2}(\ensuremath{\mathit{g}},\ensuremath{\mathit{r}})}$ algorithm, $\ensuremath{\ensuremath{\mathit{i}}}$ is one of the nodes that replaced $\ensuremath{i}'$ on the stack.) If we think of $\ensuremath{i}'$ as the parent of $\ensuremath{\ensuremath{\mathit{i}}}$, then we obtain a tree rooted at $\ensuremath{\ensuremath{\mathit{r}}}$. In Figure 12.5, this tree is a path from vertex 0 to vertex 11.

An important property of the depth-first-search algorithm is the following: Suppose that when node $\ensuremath{\ensuremath{\mathit{i}}}$ is coloured $\ensuremath{\ensuremath{\mathit{grey}}}$, there exists a path from $\ensuremath{\ensuremath{\mathit{i}}}$ to some other node $\ensuremath{\ensuremath{\mathit{j}}}$ that uses only white vertices. Then $\ensuremath{\ensuremath{\mathit{j}}}$ will be coloured first $\ensuremath{\ensuremath{\mathit{grey}}}$ then $\ensuremath{\ensuremath{\mathit{black}}}$ before $\ensuremath{\ensuremath{\mathit{i}}}$ is coloured $\ensuremath{\ensuremath{\mathit{black}}}$. (This can be proven by contradiction, by considering any path $P$ from $\ensuremath{\ensuremath{\mathit{i}}}$ to $\ensuremath{\ensuremath{\mathit{j}}}$.)

One application of this property is the detection of cycles. Refer to Figure 12.6. Consider some cycle, $C$, that can be reached from $\ensuremath{\ensuremath{\mathit{r}}}$. Let $\ensuremath{\ensuremath{\mathit{i}}}$ be the first node of $C$ that is coloured $\ensuremath{\ensuremath{\mathit{grey}}}$, and let $\ensuremath{\ensuremath{\mathit{j}}}$ be the node that precedes $\ensuremath{\ensuremath{\mathit{i}}}$ on the cycle $C$. Then, by the above property, $\ensuremath{\ensuremath{\mathit{j}}}$ will be coloured $\ensuremath{\ensuremath{\mathit{grey}}}$ and the edge $\ensuremath{(\ensuremath{\mathit{j}},\ensuremath{\mathit{i}})}$ will be considered by the algorithm while $\ensuremath{\ensuremath{\mathit{i}}}$ is still $\ensuremath{\ensuremath{\mathit{grey}}}$. Thus, the algorithm can conclude that there is a path, $P$, from $\ensuremath{\ensuremath{\mathit{i}}}$ to $\ensuremath{\ensuremath{\mathit{j}}}$ in the depth-first-search tree and the edge $\ensuremath{(\ensuremath{\mathit{j}},\ensuremath{\mathit{i}})}$ exists. Therefore, $P$ is also a cycle.

Figure 12.6: The depth-first-search algorithm can be used to detect cycles in $G$. The node $\ensuremath{\ensuremath{\mathit{j}}}$ is coloured $\ensuremath{\ensuremath{\mathit{grey}}}$ while $\ensuremath{\ensuremath{\mathit{i}}}$ is still $\ensuremath{\ensuremath{\mathit{grey}}}$. This implies that there is a path, $P$, from $\ensuremath{\ensuremath{\mathit{i}}}$ to $\ensuremath{\ensuremath{\mathit{j}}}$ in the depth-first-search tree, and the edge $\ensuremath{(\ensuremath{\mathit{j}},\ensuremath{\mathit{i}})}$ implies that $P$ is also a cycle.