Google Answers Logo
View Question
 
Q: Computer Problem 22.3-11 p 549 of Introduction to Algorithms- Cormen ( No Answer,   3 Comments )
Question  
Subject: Computer Problem 22.3-11 p 549 of Introduction to Algorithms- Cormen
Category: Computers > Algorithms
Asked by: supercomp-ga
List Price: $3.00
Posted: 26 Nov 2002 14:15 PST
Expires: 26 Dec 2002 14:15 PST
Question ID: 115066
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
Answer  
There is no answer at this time.

Comments  
Subject: Re: Computer Problem 22.3-11 p 549 of Introduction to Algorithms- Cormen
From: jkraju-ga on 27 Nov 2002 03:51 PST
 
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
Subject: Re: Computer Problem 22.3-11 p 549 of Introduction to Algorithms- Cormen
From: supercomp-ga on 27 Nov 2002 06:49 PST
 
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
Subject: Re: Computer Problem 22.3-11 p 549 of Introduction to Algorithms- Cormen
From: kennyh-ga on 26 Dec 2002 22:13 PST
 
I know that the time is expired. But, if you still need the answer. i
can supply  you the coding.

 Kenny

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy