From the book Introduction to Algorithms by Cormen ... p549
I need the answer to problem 22.3-11 which is:
Show that a depth-first search of a undirected graph G can be used to
identify the connected components of G and that the depth-first forest
contains as many trees as G has connected components. More
precisely,show how to modify depth-first search so that each vertex v
is assigned an integer label cc[v] between 1 and k where k is the
number of connected components of G, such that cc[u]=cc[v] if and only
if u and v are in the same connected component.
M

Hi supercomp-ga,
I hope this helps

1. assgin cc[i] = i+1 for all i.
2. Let g gives the no.of connected components, Initially g = 1 and
i=0;

3.Start DFS at Node i.While visiting each node in the Depth First
order do      cc[i] = g;

4.while(cc[i] <= g)	// skip visited vertices
	i++;
	
5. if( i == Total Number of vertices) go to Step 6; 
   else
   {
   	g++; 		// increment the number of connected components by 1.
   	goto Step 3;
   }
6. g gives the no.of connected components

Would you PLEASE reply in relation to the DFS(G) and DFS_visit(v)
algorithms in the text.
The question asks us to modify this pseudocodecode:
 
DFS(G)  {
for each v that exists in the set of vertexes
	color[v]=white
	predecessor[v]=NIL
while (color [v]==white for some v)
	DFS_visit(v);
}

DFS_visit(v)  {

color[v]=grey
for each u adjacent to V
if color[u] is white {
	predecessor[u]=v
	DFS_visit(u)          //recursive call 
	set color[v]=black
}


  I need to use the  DFS(G) algorithm in the text. The text already
accounts for nodes that were visited by setting the color to grey or
black and in the DFS algorithm it checks to see if the node is
white(meaning it has not been visisted) before it does a recursive
DFS_visit().
So white=not visisted
grey=visited but may have adjacent nodes that were not visisted
black =visisted and no other nodes that are reachable from this node
aare white or grey

I know that the time is expired. But, if you still need the answer. i
can supply  you the coding.

 Kenny