Depth- and Breadth-First Graph Traversals (Draft)

Objectives

  • To understand two basic graph traversals -- depth-first and breadth-first traversal
  • To see how both traversals may be implemented using essentially the same algorithm, but by using a different data structure to represent the "open list"

Preparation

As a pre-requisite for this lab activity, you should be familiar with the definition of a graph as a collection of vertices (also called nodes) and edges connecting them. Additionally you should be familiar with the two implementation strategies for a graph, namely, an adjacency matrix representation and adjacency lists.

To prepare for the actual lab activity, read the description of each of these two traversals and compare them with your textbook, if available.

The Algorithms

Visiting all vertices reachable from a designated start vertex is essential to solving many problems involving graphs and networks. For instance, suppose that we want to get from vertex H to vertex C in the network below.

Figure 1

We can proceed from vertex H to one of its immediately adjacent vertices (successor vertices). In the example above, these successor vertices are vertices B, D, and L. We thus have the start of three potential paths -- from vertex H to vertex B, from vertex H to vertex D, and from vertex H to vertex L. Vertices B, D and L are called open vertices. Open vertices are vertices to which we have found a path. We must now choose one of these paths to continue exploring as we seek to extend it to our goal, vertex C.

We will put such open vertices (and the path to which they belong) into a list of open vertices. We will then remove a vertex from this list of open vertices and generate its successors. For instance, if vertex L was the first vertex removed from this open list, vertices M and F are now open vertices along with vertex B and D. Notice that, although vertex H is a successor of vertex L, it is not reopened along with vertices M and F. Clearly reopening vertex H, a vertex for which we have already generated successors, could lead us into an infinitely cyclic path. To keep this from happening, we must keep track of which vertices have had their successors added to the list of open vertices. Such vertices are termed closed vertices; once closed a vertex cannot be reopened.

Which vertex should next have its successors generated? Clearly the answer to this question is dependent on the order in which vertices (and their associated paths) are removed from the list of open vertices. For instance, if the list of open vertices is a last-in-first-out list (that is, a stack), then the resulting search is known as a depth-first traversal. In a depth-first traversal, one path is explored as deeply as possible in the hope of finding the goal before it is abandoned in favor of another path.

PSEUDO-CODE FOR DEPTH-FIRST TRAVERSAL

/* initialization */
stack openList = { startVertex }

/* loop */
while ( closedNodes != numberOfNodes && !openList.empty())
{
  while ( openList.top() is a closed vertex ) openList.pop();

  closingVertex = openList.pop();
  increment the number of closedNodes;

  for each non-closed vertex with an edge from closingVertex
  {
    openList.push( vertex );
  }

}

Note that, even if we specify that the open list is a stack, the order in which vertices are traversed by a depth-first traversal is not uniquely determined. This is because successor vertices could be pushed on the stack in variety of orders. For example, in the graph above, the three successors of H could be pushed onto the stack in six different orders. (What are they?)

Example Trace of Depth-First

The following trace of the depth-first traversal for the graph of Figure 1 works under the assumption that successor vertices are pushed onto the open list in reverse alphabetical order. Hence, because the stack is first-in-last-out, these same successor vertices will be popped off of the stack in alphabetical order.

Vertex visited (and hence closed) Open list (stack top at left)
H B D L
B D D L
D G J D L
G J J D L
J E I M J D L
E K I M J D L
K I M J D L
I F M J D L
F A L M J D L
A L M J D L
L M M J D L
M C M J D L
C M J D L

Breadth-first variant of the algorithm

The algorithm described above, which relies upon the maintenance of an open list and a closed list, is general enough that it is not necessarily tied to a depth-first strategy. Whether or not the search strategy is depth-first depends upon how nodes are added to and removed from the open list. For example, suppose that we change the open list from a stack, as it is above, to a queue. We then get what is called a breadth-first traversal.

PSEUDO-CODE FOR BREADTH-FIRST TRAVERSAL

/* initialization */
queue openList = { startVertex }

/* loop */
while ( closedNodes != numberOfNodes && !openList.empty())
{
  closingVertex = openList.dequeue();
  increment number of closedNodes;

  for each non-closed vertex not in the openList
     and with an edge to it from closingVertex
  {
    openList.enqueue( vertex );
  }

}

Example Trace of Breadth-First

Consider how the breadth-first variant of this algorithm would process the vertices in the graph of Figure 2. Here we assume that successor vertices are enqueued in alphabetical order and hence also dequeued in alphabetical order.

Figure 2

Vertex visited (and hence closed) Open list (queue front at left)
D C E H
C E H F
E H F G I
H F G I B
F G I B A
G I B A
I B A
B A
A (empty)

Efficiency

Both the depth- and breadth-first algorithms have a general nested loop structure that resembles the following:

/* initialization */
SomeKindOfList openList = { startVertex }

/* loop */
while ( closedNodes != numberOfNodes && !openList.empty())
{
  closingVertex = openList.remove();  /* Whatever removal rule is used for the list */
  increment the number of closedNodes;

  for each non-closed vertex with an edge from closingVertex
  {
    openList.insert( vertex );       /* Whatever insertion rule is used for the list */
  }

}

If V represents the number of vertices in the graph and E the number of edges, then the efficiency of this nested loop structure will be dependent upon whether an adjacency matrix or adjacency lists are used to implement the underlying graph. If an adjacency matrix is used, then both the outer and inner loops are O(V), and hence the efficiency of the resulting algorithm is O(v2). If adjacency lists are used, then potentially the nested loop structure may have to examine every edge in the graph, so the resulting efficiency is O(E). These analyses are predicated upon the fact that removal and insertion of items into both a stack and a queue is O(1).

Compare with Your Textbook

Algorithms can appear different but still be basically identical. Compare our pseudo code with the description in your textbook (if available). Then try to answer the following questions:

  1. What effect do particular assumptions about stack and queue operations have on understanding the algorithm?
  2. Some books implement depth-first traversal recursively. Explain the difference between such a recursive implementation and the implementation using a stack that we have given

Exploring the Algorithm's Dynamic Behavior

Explore the Algorithm within JHAVÉ

You can also explore the algorithm's dynamic behavior using the algorithm visualization environment JHAVÉ. If you have not worked with JHAVÉ before, please take the time to instructions on using JHAVÉ first. If your browser is Webstart-enabled, then you may launch a visualization of the depth first algorithm directly from this depth-first link, and a visualization of breadth-first directly from this breadth-first link.

Step through each of the algorithms. Answer the questions as they appear to predict the next step. When you have reached the point where you are correctly answering the questions posed by JHAVÉ for these algorithms, try working on the Exercises below.

Exercises

  1. Trace the action of the breadth-first traversal on the graph in Figure 1
  2. Trace the action of the depth-first traversal on the graph in Figure 2
  3. In depth-first traversal, can a vertex appear in the open list more than once? Explain why or why not. What about breadth-first search -- is your answer the same?
  4. If we measure the shortness of a path between two vertices by the number of edges in that path, which of the two traversals finds shorter paths? Explain why.

Designing Data Sets

Creating input for an algorithm is an effective way to demonstrate you understanding of the algorithm behavior.

Suppose a depth-first traversal starting at node A is performed. Because nodes adjacent to a given node may be selected in different orders, the order in which nodes are visited is not unique in depth- and breadth-first traversals. Consider the following three orderings of nodes:

L1
A G H E B D C F
L2
A G H B E C F D
L3
A G B D F C E H
Construct a graph in which, allowing for adjacent nodes being selected in different orders when they are added to the open list:
  • Only L1 could be the result of a depth-first traversal starting at A
  • Only L2 could be the result of a depth-first traversal starting at A
  • L1, L2 and L3 could all be the result of a depth-first traversal starting at A
  • Only L1 and L2 could be the result of a depth-first traversal starting at A
  • Only L1 and L3 could be the result of a depth-first traversal starting at A

Then repeat the five constructions above except assume a breadth-first instead of a depth-first traversal.

Modifying the Algorithm

Create Your Own Visualization

Using your own source code, presentation software, or manually produced drawings, create your own visualization of the depth-first and/or breadth-first traversals.

Presentation

Develop a ten minute presentation on one of the traversals that uses the visualization you developed above to help you explain the nuances of the algorithm.