is it possible that the minimum cost of spanning of a weighted graph is different by Kruskal's algorithm and by Prim's algorithm?
This is a discussion on Prim's and Kruskal's minimum cost spanning tree within the General Discussions forums, part of the Community Boards category; is it possible that the minimum cost of spanning of a weighted graph is different by Kruskal's algorithm and by ...
is it possible that the minimum cost of spanning of a weighted graph is different by Kruskal's algorithm and by Prim's algorithm?
Moved to General Discussions.
It seems to me that if two algorithms with equivalent input arrive at different conclusions about the same deterministic property, then one or both algorithms must be incorrect (or the input is invalid).
Last edited by laserlight; 04-24-2011 at 12:43 PM.
C + C++ Compiler: MinGW port of GCC
Version Control System: Bazaar
Look up a C++ Reference and learn How To Ask Questions The Smart Way
The algorithms can give you different (equal cost) trees. (In fact, two different implementations of the same algorithm could give you different results.) This can happen because there may be more than one minimal cost tree (a minimal spanning tree is not necessarily unique).
Consider this graph.
A -> B
B -> C
A -> C
I can get the tree A -> B, A -> C or the tree A->B, B->C. If all edges have weight 1 then there are two minimal trees.
Good elaboration, but I note that the main part that answers the question is "(equal cost) trees", i.e., the value of the property (minimum cost of spanning of a weighted graph) is the same either way.Originally Posted by Perspective
C + C++ Compiler: MinGW port of GCC
Version Control System: Bazaar
Look up a C++ Reference and learn How To Ask Questions The Smart Way