is it possible that the minimum cost of spanning of a weighted graph is different by Kruskal's algorithm and by Prim's algorithm?

Printable View

- 04-24-2011gaurav9991Prim's and Kruskal's minimum cost spanning tree
is it possible that the minimum cost of spanning of a weighted graph is different by Kruskal's algorithm and by Prim's algorithm?

- 04-24-2011laserlight
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). - 04-25-2011gaurav9991
thanks. I got it.

- 04-26-2011Perspective
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. - 04-26-2011laserlightQuote:

Originally Posted by**Perspective**