FemaleDuck
New Naija
Karma: 0
 Offline
Posts: 9
|
 |
« on: May 23, 2009, 04:18:48 AM » |
|
I just want to make sure I understand prim's algorithm correctly
Given the graph with AB=3, BC=4, CD=4,AD=1,AE=7, CE=3,BE=6,AC=3. Show step by step how the algorithm finds the minimal spanning tree.
so lets say for argument sake that the start node is A. I have four choices. (A,B)(A,D)(A,E)(A,C). Since the shortest distance is (A,D) I choose that branch. Now I would see what the shortest distance from D is. I only have one choice which is (D,C) so I would then add that branch. Now from C I have to choices because (C,E)and (C,A) both have the same distance. However going to A would create a closed loop which is not allowed in a minimal spannng tree.
Am I on the right track? If not can someone please explain how to do this.
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
|
