360 CHAPTER 6 Graph Theory
INPUT: Graph G = (V, E)
OUTPUT: For each vertex, a number labeling its connected componentCreate an array Visited[ 1.. I V I] with I V I positions each initialized
to FALSE
Create an array Comp with I V I positions each initialized to 0
/* Comp [v] holds the integer label of v's component */
CompNumber = 0 /* No components discovered yet *!
for v = I to I V1 do
/* Make sure each vertex gets visited "/
if (Visited [v] = FALSE) then /* New component! "1
Add 1 to CompNumber
I* CompNumber is the number of the new component */
DfsComp(G, v, Visited, Comp, CompNumber)
/* Explore the new component starting at v *!DfsComp(G, v, Visited, Comp, CompNumber)
/* The recursive procedure "/
Comp [v] = CompNumber
/* Record the number of v's component *1
Visited [v] = TRUE
for each vertex w adjacent to v do
if (Visited [w] ) = FALSE then
DfsComp(G, w, Visited, Comp, CompNumber)The procedure DfsComp is a slight modification of the earlier procedure called Dfs.
The difference is that this algorithm ensures every vertex in the graph is eventually exam-
ined, even if the graph is not connected.
A better understanding of the roles of the arrays and variables in DfsComp will help
to show how the procedure operates. The variables Visited, Comp, and CompNumber im-
plement one way to keep track of what is learned by DfsComp at a vertex. At the end of
the algorithm's execution, all vertices with the same value in Comp have been identified
as belonging to the same connected component. The array Visited keeps track, as the al-
gorithm is executed, of whether a vertex has been examined. If Visited has a value TRUE
for a vertex, then it follows that Comp has been assigned a value for that vertex. Because
Visited only has its value changed once for each vertex, Comp is assigned exactly one value
for each vertex. The variable CompNumber is used to make sure that the same number is
assigned to each vertex in a particular component and that vertices in different components
are identified by different numbers.