Discrete Mathematics for Computer Science

Connected Graphs 357

contradicts the assumption that a vertex such as w exists. Therefore, the algorithm is exe-

cuted for each vertex of G, and the algorithm is correct.

6.7.3 Complexity of Dfs

The analysis of the complexity of this search method is restricted to the case of connected

graphs. The generalization to disconnected graphs is left for the reader. Also, assume that

a graph has an adjacency list representation. The analysis for the case using an adjacency

matrix representation for the graph is also left to the reader.

In proving the correctness of Dfs, we showed that for a graph G = (V, E), the proce-

dure Dfs is called I V I times, once for each vertex of G. We can calculate the complexity

of Dfs by adding up the time taken by each of these I V I calls to Dfs. There are two parts

to each call, the marking process and the for loop. The marking process takes a constant

amount of time-say, cl. Each time through the loop, the for loop takes a constant amount

of time to test the condition-say, c2-and a constant amount of time-say, c3-as an up-

per bound for the time to execute the body of the loop (that is, to test the condition and

make the recursive call to Dfs when the condition is TRUE). For each vertex, the loop

will be executed once for each entry on the vertex's adjacency list. The total time to exe-

cute the loop for a single vertex v is bounded by cl + (c2 + c 3 )deg(v). Summing the time

taken by each of the calls to Dfs gives an upper bound on the complexity of Dfs. Since

ZVEV deg(v) = 2- I E I by Theorem^2 in Section 6.2, we have

Running time of Dfs on G < Z(Cl + (C2 + c3)deg(v))

VEV

<cl C V I + (c2 + C3) 1deg(v)

vGV

< Cl • IV I+ (c 2 + C3) .2. I E I

=O(IVI+IEI)

Observe that this argument does not just count operations. It uses results about graphs

to provide a more careful analysis.

6.74 Breadth First Search

A breadth first search is one of the simplest algorithms for searching a graph. The range of
effective applications of this search method is quite different from the range of applications
typically used with a depth first search.
A typical problem using a breadth first search involves finding an optimal path between
two vertices. When the edges have weights, you might be asking how much information
can flow from one computer to another if the information passes through a number of
computers with different capacities. If the vertices represent plants or warehouses or retail
stores, you might be asking if you can supply each store with all the product they can sell.
When researching a family genealogy, this search could be used to print out the members of
the family tree, one generation at a time. For example, the family tree shown in Figure 3.2
(see Section 3.1) would have its members printed in the order Mary, John, Peter, Elaine,