Can Prims and Kruskals algorithm yield different min spanning tree?

Question

In this problem I am trying to find the min weight using the Prims and Kruskals and list the edges in the order they are chosen.

For Prims I am getting order (A,E), (E,F), (F,C), (C,D), (C,B) with a weight of 21

With Kruskals I get (C,F), (A,E), (C,D), (B,C) with a weight of 14

I feel like I shoudnt be getting two different min weights. Could the problem be that I am forced to start at Vertex A when using Prims? If that is not my problem what is?

Answer 1

You messed up with Kruskal's algorithm, since the answer you give isn't even a tree: there is, for example, no path between A and B.

Answer 2

In general:

• If the edge weights in your graph are all different from each other, then your graph has a unique minimum spanning tree, so Kruskal's and Prim's algorithms are guaranteed to return the same tree.
• If the edge weights in your graph are not all different (as in your example, where $(A,B)$ and $(D,E)$ both have weight 9), then neither algorithm is necessarily deterministic. They both have steps of the form "choose the lowest-weight edge that satisfies some condition" that might yield ambiguous results. For example, in the extreme case where all edges have the same weight, either algorithm could conceivably return any of the graph's spanning trees. That is, Prim's algorithm might yield a different minimum spanning tree than Kruskal's algorithm in this case, but that's because either algorithm might yield a different minimum spanning tree than (a different implementation of) itself!