CS 3343/3341
 Analysis of Algorithms 
  Graph Search   
   Breadth- and Depth-First  

Introduction. Students in this course are usually familiar with traversals of binary search trees. There are three kinds: preorder, inorder, and postorder. Of these, the inorder traversal presents the elements of a binary search in the order used for the tree, so it is usually the most important. However, one common task is to visit each node of the tree in turn for a variety of purposes.

For example, in the syntax tree often used by compilers, one sometimes uses a complete traversal, illustrated below for the simple search tree made up of days of the week. Here we start at the root and go all the way around the tree, visiting each node three times. The three kinds of traversals are included: preorder in blue, inorder in green, and postorder in orange.


Complete Tree Traversal (click picture or days.pdf).		   
CompleteTraversal(root);

CompleteTraversal(node x) {
     if (x != null) {
          blue visit (preorder);
          CompleteTraversal(x.left);
          green visit (inorder);
          CompleteTraversal(x.right);
          orange visit (postorder);
     }
}

   
Monday
Friday
Friday
Friday
Monday
Tuesday
Thursday
Saturday
Saturday
Sunday
Sunday
Sunday
Saturday
Thursday
Thursday
Tuesday
Wednesday
Wednesday
Wednesday
Tuesday
Monday

Compilers use this kind of traversal during semantic analysis, where information can be passed down the tree (inherited) and passed up the tree (synthesized). It is also possible to leave important information at a node during the first or second visit, and pick it up or use it during a later visit.

Graph Search. Graphs are much less uniformly structured than trees, yet we still want to visit all their vertexes and investigate them. There are two kinds of traversals (called searches) of graphs: breadth-first search and depth-first search. Breadth-first search uses a queue, while there are two versions of depth-first search, one using a stack and one using recursion.

All these searches go from vertex to vertex, until all reachable vertexes are visited. In your text's notation, all vertexes are initially "unvisited", which is denoted by the color WHITE. As soon the program arrives at a vertex, its color turns to GRAY, and remains GRAY until the program is done with the vertex, when as a last act, the program turns it BLACK.

During the course of working with a newly discovered vertex u, the program looks at all vertices v on the adjacency list for u. In case v is WHITE, the edge (u, v) is added to the growing spanning tree for the graph. For breadth-first search, each such WHITE v is put into the queue. For depth-first search, each WHITE v is put into the stack, or else for each WHITE v the program calls itself recursively from v.

Your text's Breadth-First Search Algorithm. (See text, pages 594-602) Here is the pseudo-code for this algorithm, which uses a queue. This algorithm starts from a single source vertex s and covers all vertices reachable from s.


BFS Algorithm (click picture or here for full size image)

Here is your text's example of this search in action:


BFS Example (click picture or here for full size image)

Your text's Depth-First Search Algorithm. Here is the pseudo-code for this algorithm, which uses recursion. Unlike your text's BFS algorithm, this one starts from any WHITE vertex and can handle graphs with more than one component. We will sometimes ignore this feature when there is a single start vertex (the "root" vertex) from which all other vertices are reachable. Your text's topological sort algorithm uses the more general form.


DFS Algorithm (click picture or here for full size image)

Here is your text's example of this search in action:


DFS Example (click picture or here for full size image)

Depth-First Search Algorithm that uses a Stack. This algorithm is like a mash-up of the previous two algorithms, where in place of a recursive call, the program pushes each new WHITE vertex onto a stack.

Illustrations of Searches.

Shortest Paths. Here the length of each path is just the number of edges. You can think that the weight of each edge is 1. (Right now we are ignoring the "distance" weight on the edges of the US Capitals graph.) Assume you have carried out a Breadth-First Search, starting from vertex s. The the following algorithm (text, page 601) prints a shortest path from s to some vertex v. (Notice the phrase "a shortest path". In general there may be many paths of the same length, but only one will be specified by the spanning tree.)

Print-Path(s, v)
     if v == s
          print s
     elseif v.π == NIL
          print "no path from" s "to" v
     else Print-Path(s, v.π)
          print v

This path is constructed backwards along the path v to v.π to (v.π).π to ... to s.

Revision date: 2012-10-31. (Please use ISO 8601, the International Standard Date and Time Notation.)