Minimum spanning tree - Prim's algorithm

Question

I have to demonstrate Prim's algorithm for an assignment and I'm surprised that I found two different solutions, with different MSTs as an outcome. Now I now that shouldn't happen, so I wonder what I did wrong ?

Here is the exercise: Prim's Algorithm

The first solution (using Prim's) is visiting the nodes in the following order: v0,v1,v8,v7,v6,v3,v2,v4,v5 Here the MST has a weight of 37, which is the same result that I got by using Kruskal's on the same graph.

The second solution (again using Prim's) however is the following order of visited notes: v0,v1,v3,v2,v7,v8,v6,v4,v5 , which leads to a MST with a weight of 39. How can this be ? Where is my mistake ?

Thanks in advance

• Raphael: Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
• Raphael: Why do you expect Prim's algorithm to even always yield the same result, let alone the same execution trace?
• Phreneticus: Well, I don't expect it to yield the same result as in the exact same minimal spanning tree. But I expect it to yield ONE minimal spanning tree in a set of minimal spanning trees, which all have the same total weight. Am I wrong there ?

Answer 1

Prim's algorithm could give different solutions (depending on how you resolve "ties"), but all solutions should give a MST with the same (minimal) weight, which is not the case here.

Your second solution: $v_0,v_1,v_3,v_2,v_7,v_8,v_6,v_4,v_5$ is incorrect. After adding $v_0,v_1,v_3,v_2$ you add $v_7$. But the minimum distance between $v_7$ and any existing vertex in the tree is 6ドル$. Vertex $v_6$ however has a distance of only 4ドル,ドル and should thereby be added first.

You could continue this, and end up with a solution that is indeed different from your solution 1, but has the same weight. For example, $v_0,v_1,v_3,v_2, v_6, v_7,v_8,v_4,v_5,ドル which gives an MST of weight 37ドル,ドル as expected.