Find a minimum spanning tree using Prim's algorithm

Question

I have the adjacency matrix: Where we have nodes a to g, and with their respective weights x means symmetry, and the spaces left out are positive infinity

$$\begin{array}{c|c|c|c|c|c|c|c|} & \text{a} & \text{b} & \text{c}& \text{d}& \text{e}& \text{f} & \text{g}\\ \hline \text{a} & x & 7& &5\\ \hline \text{b} & 7& x &8 &9&7 \\ \hline \text{c} & &8&x&&5 \\ \hline \text{d} &5&9&&x&15&6\\ \hline \text{e} &&7&5&15&x&8&9 \\ \hline \text{f} &&&&6&8&x&11\\ \hline \text{g} &&&&&9&11&x\\ \hline \end{array}$$

This is my attempt at prim's algorithm:

Initialization:

$u,v$ $List$

$-$ {a}

$(a,d)$ {a,d}

$(d,f)$ {a,d,f}

$(f,e)$ {a,d,e,f}

$(e,c)$ {a,c,d,e,f}

$(e,b)$ {a,b,c,d,e,f}

$(e,g)$ {a,b,c,d,e,f,g}

But I'm not sure about the minimum spanning tree, is this correct at all?

Answer 1

To stick with your notation:

$(a,d)\ \{a,d\}$

$(d,f)\ \{a,d,f\}$

$(a,b)\ \{a,b,d,f\}$

$(b,e)\ \{a,b,d,e,f\}$

$(c,e)\ \{a,b,c,d,e,f\}$

$(e,g)\ \{a,b,c,d,e,f,g\}$

Making the total cost $5+6+7+7+5+9=39$. You went wrong in the third step, where you added $(f,e)$ instead of $(a,b)$.

NB: Draw it yourself, check that you understand each step and verify that it is correct :)

Answer 2

If you first draw the complete tree from the matrix then using Prim's algorithm you just add the egde with the lowest value to the minimum spanning tree and continue doing so until all vertices are connected to the minimum spanning tree (of course you should'nt add any edge if it doesn't add another vertice to the tree). I personally think that it is a lot easier to think about it this way