Algorithme de prim - malentendu

Question

Je dois démontrer l'algorithme de Prim pour une affectation et je suis surpris d'avoir trouvé deux solutions différentes, avec des MST différents comme résultat. Maintenant, je ne devrais pas arriver, alors je me demande ce que j'ai fait de mal?

Voici l'exercice:

La première solution (en utilisant les prim) consiste à visiter les nœuds dans l'ordre suivant: V0, V1, V8, V7, V6, V3, V2, V4, V5 Ici, le MST a un poids de 37, ce qui est le même résultat que j'ai obtenu en utilisant Kruskal sur le même graphique.

La deuxième solution (à nouveau en utilisant les prim) est cependant l'ordre suivant des notes visitées: V0, V1, V3, V2, V7, V8, V6, V4, V5, ce qui mène à un MST avec un poids de 39. Comment peut-il être ? Où est mon erreur?

Merci d'avance