# Prim's algorithm - misunderstanding

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:

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 ?

• 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 Jan 23 '18 at 11:53
• Why do you expect Prim's algorithm to even always yield the same result, let alone the same execution trace? – Raphael Jan 23 '18 at 11:54
• 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 ? – Phreneticus Jan 23 '18 at 12:08

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.