Discrete Mathematics for Computer Science

358 CHAPTER 6 Graph Theory

Maude, Harold, George, and Elizabeth if a breadth first search was used. Even the Job

Assignment Problem introduced in Section 6.1 can be effectively solved using this search

procedure as part of the algorithm.

When a depth first search starts at a vertex v and finds a vertex w with Visited[w] =

FALSE, no other adjacency of v will be examined until all the adjacencies of w have been

examined. In contrast, a breadth first search examines all the vertices adjacent to a vertex

before any vertex not adjacent to that vertex is examined. A temporary storage area is used

to store vertices for later processing. This storage area is managed as a list, with entries

being added at the end and removed from the front (this is formally known as a queue, or

a first-in-first-out list, which we only need to deal with intuitively here).

To implement a breadth first search of a graph G = (V, E), examine the vertices and

edges of G as follows. For getting started, first mark all the vertices as "unvisited." Choose

any vertex-say, v. Mark v as "visited," and put it on the end of the list. Now, for each

vertex on the list, examine in some order all the vertices adjacent to v. When all the "un-

visited" vertices adjacent to v have been marked as "visited" and put on the end of the

list, remove the vertex from the front of the list and repeat this procedure for any of its

adjacencies that are marked as "unvisited." Continue this procedure until the list is empty.

A breadth first search will be performed on the graph used in the depth first search

example so that it will be easier to see the differences between the search procedures. As

with a depth first search, a breadth first search tree can be defined. One way to see the

differences between these two search procedures is to notice the difference between the

structure of the depth first search tree shown in Figure 6.23 and the corresponding breadth

first search tree shown in Figure 6.24. The same convention for tree edges and all other

edges explained for a depth first search are used for a breadth first search.

Lists of

Vertices Adjacencies

a b c

b b a d g

c a deg

9d cb f

\\/,,,,,-c e c f

f e d

d g h bchg

Breadth First Search Breadth First

Beginning at a Search Tree

a a

b c bC

d d

f hf h

Figure 6.24 Breadth first search and breadth first search tree.