To write the breadth-first search algorithm in an elegant fashion, we will use a
queue structure. A queue is simply a line in which new arrivals are added at the back
and departures take place at the front. A checkout line in a grocery store is an example
of a queue of customers—a new customer joins the line at the back and departures
take place from the front of the line as customers are checked through. The addition of
an entry at the back of a queue is called an enqueue operation, and a departure from
the front of the queue is called a dequeue operation. Thus the notation enqueue(a, Q)
denotes adding a to the end of a queue called Q, and dequeue(Q) denotes removal of
the entry currently at the front of Q. We’ll also use a function front(Q), which returns
the value of the entry currently at the front of Q but does not remove that entry. In the
following algorithm, the input is a simple, connected graph G and a specified node a;
the output is a list of all nodes in G in breadth-first order from a.
algoRitHm BrEaDthFirst
BreadthFirst(simple, connected graph G; node a);
//writes nodes in graph G in breadth first order from node a
Local Variable:
queue of nodes Q
initialize Q to be empty
mark a visited
write(a)
enqueue(a, Q)
while Q is not empty do
for each node n adjacent to front(Q) do
if n not visited then
mark n visited
write(n)
enqueue(n, Q)
end if
end for
dequeue(Q)
end while
end BreadthFirst
example 12
Let’s walk through the algorithm for a breadth-first search of the graph of Figure
7.15 beginning at node a (this is the same graph on which we did the depth-first
search in Example 11). We begin by initializing an empty queue Q, marking node a
as visited, writing it out, and adding it to the queue. When we first reach the while
loop, the queue is not empty and a is the entry at the front of the queue. In the for
loop, we look for unvisited nodes adjacent to a to visit, write them out, and add
them to the back of the queue. We may have a choice of nodes to visit here; as before, and purely as a convention, we will agree to visit them in alphabetical order.
Thus the first time we complete the for loop, we have visited and written out b, e,
h, and i, in that order, and added them to the queue. The graph at this point looks
Section 7.4 Traversal Algorithms
599
queue structure. A queue is simply a line in which new arrivals are added at the back
and departures take place at the front. A checkout line in a grocery store is an example
of a queue of customers—a new customer joins the line at the back and departures
take place from the front of the line as customers are checked through. The addition of
an entry at the back of a queue is called an enqueue operation, and a departure from
the front of the queue is called a dequeue operation. Thus the notation enqueue(a, Q)
denotes adding a to the end of a queue called Q, and dequeue(Q) denotes removal of
the entry currently at the front of Q. We’ll also use a function front(Q), which returns
the value of the entry currently at the front of Q but does not remove that entry. In the
following algorithm, the input is a simple, connected graph G and a specified node a;
the output is a list of all nodes in G in breadth-first order from a.
algoRitHm BrEaDthFirst
BreadthFirst(simple, connected graph G; node a);
//writes nodes in graph G in breadth first order from node a
Local Variable:
queue of nodes Q
initialize Q to be empty
mark a visited
write(a)
enqueue(a, Q)
while Q is not empty do
for each node n adjacent to front(Q) do
if n not visited then
mark n visited
write(n)
enqueue(n, Q)
end if
end for
dequeue(Q)
end while
end BreadthFirst
example 12
Let’s walk through the algorithm for a breadth-first search of the graph of Figure
7.15 beginning at node a (this is the same graph on which we did the depth-first
search in Example 11). We begin by initializing an empty queue Q, marking node a
as visited, writing it out, and adding it to the queue. When we first reach the while
loop, the queue is not empty and a is the entry at the front of the queue. In the for
loop, we look for unvisited nodes adjacent to a to visit, write them out, and add
them to the back of the queue. We may have a choice of nodes to visit here; as before, and purely as a convention, we will agree to visit them in alphabetical order.
Thus the first time we complete the for loop, we have visited and written out b, e,
h, and i, in that order, and added them to the queue. The graph at this point looks
Section 7.4 Traversal Algorithms
599