50. Minimum Spanning Trees (MST - Arbres Couvrants de Poids Minimum) : Concept de l'Algorithme de Prim

Un Spanning Tree (Arbre Couvrant) d'un graphe est un sous-graphe qui connecte tous les sommets ensemble, sans aucun cycle. Un Minimum Spanning Tree (MST) est un arbre couvrant où la somme des poids des arêtes est minimisée.

Algorithme de Prim (Approche Gloutonne)

L'algorithme de Prim construit le MST de manière itérative en ajoutant des arêtes qui connectent un nouveau sommet à l'ensemble d'arbres en croissance. C'est une stratégie d'optimisation locale.

1. Commencer par un sommet source S arbitraire dans le MST.
2. Répéter V-1 fois :
   • Sélectionner l'arête (U, V) qui connecte un sommet U déjà dans le MST à un sommet non visité V tel que le poids de l'arête (U, V) soit minimal.
   • Ajouter cette arête de poids minimum et le sommet V au MST.

Prim's est implémenté efficacement à l'aide d'un Min Heap (File de Priorité), tout comme Dijkstra's, pour sélectionner rapidement l'arête suivante la plus petite.