600
Graph Algorithms
like Figure 7.15. We then remove a from the front of the queue, which as a result
contains (from front to back)
b, e, h, i
In the next iteration of the while loop, b is the front element in the queue, and the
for loop searches for unvisited nodes adjacent to b. The only previously unvisited
node here is c, which gets marked as visited, written out and added to the queue.
After removing b, the queue contains
e, h, i, c
Performing the while loop again, e is at the front of the queue. A search of the
nodes adjacent to node e produces one new node, node j. The graph now looks like
Figure 7.16, and after removing e the queue contains
h, i, c, j
Figure 7.16
When searching for nodes adjacent to h, we pick up one new node, node k. When
searching for nodes adjacent to i, no new nodes are added to the queue. When c
becomes the first element in the queue, a search for nodes adjacent to c turns up
two new nodes, d and f. After adding these to the queue (and removing c), the
queue contains
j, k, d, f
Looking for nodes adjacent to j and then to k adds no new nodes to the queue.
When the front of the queue is d, a new node g is found, and the queue (after removing d ) is
f, g