Algoritmo di Prim - malinteso

Question

Devo dimostrare l'algoritmo di Prim per un incarico e sono sorpreso di aver trovato due diverse soluzioni, con MST diverse come risultato. Ora ora non dovrebbe accadere, quindi mi chiedo cosa ho fatto di sbagliato?

Ecco l'esercizio:

La prima soluzione (usando Prim's) è visitare i nodi nel seguente ordine: V0, V1, V8, V7, V6, V3, V2, V4, V5 Qui il MST ha un peso di 37, che è lo stesso risultato Usando Kruskal sullo stesso grafico.

La seconda soluzione (di nuovo usando Prim) è tuttavia il seguente ordine delle note visitate: V0, V1, V3, V2, V7, V8, V6, V4, V5, che porta a un MST con un peso di 39. Come può essere questo ? Dov'è il mio errore?

Grazie in anticipo