Discrete Mathematics for Computer Science

Connected Graphs 359

INPUT: Connected graph G = (V, E), and start vertex v0

RESULT: Each vertex and each edge is examined

Create an array Visited with I V I positions initialized to FALSE

Create a queue Q that is initially empty

/* Q holds the discovered vertices waiting to be processed *!

Bfs(G, vo, Visited, Q) I* Start the search at vo */

Bfs(G, v, Visited, Q) /* The recursive procedure */

Visited [v] = TRUE

Put v at the end of Q

while Q # 0

Remove the vertex w at the front of Q

for each vertex u adjacent to w do

if (Visited [ u ] = FALSE) then

Visited [ u ] = TRUE

Put u at the end of Q

By very similar arguments to the ones used for the depth first search, the reader

can prove that this algorithm is correct and that the complexity of Bfs is also

0(1 V I + I E 1).

6.7.5 Finding Connected Components

One use of connectedness in many graph algorithms is to find the components of a graph
and then solve a problem for each of the components separately. Since the components can
be found in O(1 E I + I V I) time, this operation does not affect the overall complexity of an
algorithm that must typically examine each vertex and each edge in a graph to determine
an answer.
The algorithm presented for finding connected components uses a depth first search
of the graph to find the components one at a time. The adjacency list representation of a
graph makes the depth first search particularly easy to implement. The procedure to find the
Connected Components that calls DfsComp uses a counter (CompNumber) to keep track of
how many connected components are found in the graph being processed. If all the vertices
are visited as a result of the first call to DfsComp, then this counter will have a value of 1
after the process is finished. In this case, the graph is connected.