Prim'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?

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).

thanks. I got it.

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.

Quote:

---

Originally Posted by Perspective

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).

---

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.