Les algorithmes de Kruskal et Prim produisent-ils le même arbre couvrant minimum?

En supposant que les bords ne sont pas orientés, ont un poids unique et aucun chemin négatif, ces algorithmes produisent-ils les mêmes arbres couvrant minimum?

Trouvé ceci qui indique que si toutes les conditions que j'ai mentionnées ci-dessus sont remplies, un graphique a nécessairement un MST unique. Par conséquent, en termes de ma question, les algorithmes de Kruskal et Prim produisent nécessairement le même résultat.

Si le MST est unique, tous les algorithmes vont forcément le produire.

Si le MST n'est pas unique, les sorties peuvent différer en raison de différents ordres de traitement des nœuds (même deux implémentations distinctes du même algorithme peuvent), mais les poids totaux seront identiques. Dans ce cas, le MST est un terme impropre.

Pour compléter la réponse d' Yves Daoust , le graphique suivant

Dans ce graphique, nous avons 3 nœuds et 3 arêtes, chacun a le même poids. De toute évidence, 2 arêtes formeront un MST pour ce graphique. Cependant, les deux bords choisis dépendront non seulement de l'algorithme, mais de la mise en œuvre de l'algorithme. Par exemple, si je stocke les nœuds dans une liste, je peux les visiter dans un ordre différent que si j'ai stocké les nœuds dans un ensemble, même si j'utilise le même algorithme MST à partir de ce moment.

En fait, si mon implémentation repose sur l'arithmétique des pointeurs (ce que font certains conteneurs dans certaines langues), je peux même choisir un MST différent chaque fois que j'exécute l'algorithme!