Processing f and then g yields no new nodes. After g is removed from the queue,
the queue is empty. The while loop—as well as the algorithm—terminates. The list
of nodes written out by this process, that is, the nodes in breadth-first order from
a, are
a, b, e, h, i, c, j, k, d, f, g
Like the depth-first search, the breadth-first search is not difficult to trace; one
must just keep track of the nodes that have been visited and the current contents
of the queue.
Analysis
How much work do the depth-first search and breadth-first searches perform?
Both algorithms look for all unvisited nodes adjacent to a given node. Suppose
the graph contains n nodes and m arcs. One of the advantages of representing a
graph as an adjacency list rather than an adjacency matrix is that this particular
operation is more efficient; to find nodes adjacent to node i requires traversing i’s
adjacency list, which may be short, rather than traversing row i of the adjacency
matrix, which must contain n entries. Therefore we will assume an adjacency list
representation of the graph.
In breadth-first search, the algorithm searches all at one time the entire adjacency list of the node at the front of the queue, marking, writing out, and enqueuing the unvisited nodes found. In the depth-first search, the algorithm may be
interrupted many times while traversing the adjacency list of a given node to go
off (by virtue of the recursion) and process sections of the adjacency lists of other
nodes. Eventually, however, every adjacency list is completely covered.
Traversing the adjacency lists of the graph drives the amount of work done in
either search. There are n adjacency lists, so the amount of work is at least Θ(n)
because each adjacency list must be checked. Because there are m arcs, the work
in traversing the total length of all the adjacency lists is at least Θ(m). Therefore
both depth-first search and breadth-first search are Θ(max(n, m)) algorithms. If
there are more arcs than nodes (the usual case), then Θ(max(n, m)) = Θ(m).
Applications
Depth-first search and breadth-first search can be used as the basis for performing
other graph-related tasks, some of which we have solved before. A nonrooted tree
structure that is a subgraph of the original graph can be associated with each search.
When traversing node i’s adjacency list, if node j is adjacent to i and is previously
unvisited, then the i–j arc is added to this subgraph. Because no arc to a previously
visited node is used, cycles are avoided and the subgraph is a nonrooted tree. Because all nodes ultimately are visited (for the first time), these trees are spanning
trees for the graph. Each tree has n − 1 arcs, the minimal number of arcs to connect
n nodes. Here we are assuming that arcs are unweighted, but if we consider them to
be weighted arcs, each with weight 1, then these trees are minimal spanning trees.
Section 7.4 Traversal Algorithms
601
praCtiCe 15 Write the nodes in a breadth-first search of the graph in Figure 7.14, beginning with node a. ■
the queue is empty. The while loop—as well as the algorithm—terminates. The list
of nodes written out by this process, that is, the nodes in breadth-first order from
a, are
a, b, e, h, i, c, j, k, d, f, g
Like the depth-first search, the breadth-first search is not difficult to trace; one
must just keep track of the nodes that have been visited and the current contents
of the queue.
Analysis
How much work do the depth-first search and breadth-first searches perform?
Both algorithms look for all unvisited nodes adjacent to a given node. Suppose
the graph contains n nodes and m arcs. One of the advantages of representing a
graph as an adjacency list rather than an adjacency matrix is that this particular
operation is more efficient; to find nodes adjacent to node i requires traversing i’s
adjacency list, which may be short, rather than traversing row i of the adjacency
matrix, which must contain n entries. Therefore we will assume an adjacency list
representation of the graph.
In breadth-first search, the algorithm searches all at one time the entire adjacency list of the node at the front of the queue, marking, writing out, and enqueuing the unvisited nodes found. In the depth-first search, the algorithm may be
interrupted many times while traversing the adjacency list of a given node to go
off (by virtue of the recursion) and process sections of the adjacency lists of other
nodes. Eventually, however, every adjacency list is completely covered.
Traversing the adjacency lists of the graph drives the amount of work done in
either search. There are n adjacency lists, so the amount of work is at least Θ(n)
because each adjacency list must be checked. Because there are m arcs, the work
in traversing the total length of all the adjacency lists is at least Θ(m). Therefore
both depth-first search and breadth-first search are Θ(max(n, m)) algorithms. If
there are more arcs than nodes (the usual case), then Θ(max(n, m)) = Θ(m).
Applications
Depth-first search and breadth-first search can be used as the basis for performing
other graph-related tasks, some of which we have solved before. A nonrooted tree
structure that is a subgraph of the original graph can be associated with each search.
When traversing node i’s adjacency list, if node j is adjacent to i and is previously
unvisited, then the i–j arc is added to this subgraph. Because no arc to a previously
visited node is used, cycles are avoided and the subgraph is a nonrooted tree. Because all nodes ultimately are visited (for the first time), these trees are spanning
trees for the graph. Each tree has n − 1 arcs, the minimal number of arcs to connect
n nodes. Here we are assuming that arcs are unweighted, but if we consider them to
be weighted arcs, each with weight 1, then these trees are minimal spanning trees.
Section 7.4 Traversal Algorithms
601
praCtiCe 15 Write the nodes in a breadth-first search of the graph in Figure 7.14, beginning with node a. ■