Analysis of Algorithms : An Active Learning Approach

152 GRAPH ALGORITHMS

the graph, it is possible for a node to be on two paths of different lengths

from the starting node. Because we will visit that node for the first time

along the shortest path from the starting node, we will not need to consider

it again. We will, therefore, either need to keep a list of the nodes we have

visited or we will need to use a variable in the node to mark it as visited to

prevent multiple visits.

Consider again the graph in Fig. 6.4. If we begin our traversal at node 1, we

will visit nodes 2 and 8 on the first pass. On the second pass, we will visit

nodes 3 and 7. (Even though nodes 2 and 8 are also at the end of paths of

length 2, we will not return to them because they were visited in the first pass.)

On the third pass, we visit nodes 4 and 5, and on the last pass we visit nodes 6

and 9.

Where the depth-first traversal depended on a stack, our breadth-first tra-

versal is based on a queue. The algorithm for breadth-first traversal is

BreadthFirstTraversal(G, v)

G is the graph

v is the current node

Visit( v )

Mark( v )

Enqueue( v )

while the queue is not empty do

Dequeue( x )

for every edge xw in G do

if w is not marked then

Visit( w )

Mark( w )

Enqueue( w )

end if

end for

end while

This algorithm will add the root of the breadth-first traversal tree to the

queue but then immediately remove it. As it looks at the nodes that are adja-

cent to the root, they will be added to the end of the queue. Once all of the

nodes adjacent to the root have been visited, we will return to the queue and

get the first of those nodes. You should notice that because nodes are added to

the end of the queue, no node that is two edges away from the root will be