|
|
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 |
|
There is no answer at this time. |
|
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 |
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 Home - Answers FAQ - Terms of Service - Privacy Policy |