JHAVÉ Java-Hosted Algorithm Visualization Environment |

Home | Learners | Instructors | Developers | Download |

## 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"
## PreparationAs 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 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 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
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 ## 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-FirstThe 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.
## Breadth-first variant of the algorithmThe 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-FirstConsider 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
## EfficiencyBoth 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(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 TextbookAlgorithms 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: - What effect do particular assumptions about stack and queue operations have on understanding the algorithm?
- 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 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- Trace the action of the breadth-first traversal on the graph in Figure 1
- Trace the action of the depth-first traversal on the graph in Figure 2
- 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?
- 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 SetsCreating 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
- 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 VisualizationUsing your own source code, presentation software, or manually produced drawings, create your own visualization of the depth-first and/or breadth-first traversals. ## PresentationDevelop 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. |