« Computing the cost (due 1/21) | Main | Parts of a Greedy Crossing the Desert Algorithm (due 1/24) »
January 21, 2005
Prim's algorithm on a disconnected graph
What happens if Prim's algorithm is deployed on a disconnected graph? A disconnected graph has some nodes that are not connected to any other nodes.
Posted by jones at January 21, 2005 02:33 PM
Comments
It seems that if Prim's is run on a disconnected graph that one of two things would happen depending on how the algorithm is coded:
1. You will get a minimum spanning tree for the part of the graph which contains the shortest edge.
2. The program will crash because there will be no edge to add to the solution set once the subsection of the graph containing the shortest edge has been mapped.
This is only my intuition. Anyone have any other ideas?
Posted by: Matt Doyle ![[TypeKey Profile Page]](http://vv.cs.byu.edu/cs312-003/nav-commenters.gif)
at February 8, 2005 11:33 PM
Post a comment
Thanks for signing in, . Now you can comment. (sign out)
(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)