Algorithme de Prim - Prim's algorithm

Une démo de l'algorithme de Prim basé sur la distance euclidienne

En informatique , l'algorithme de Prim (également connu sous le nom d'algorithme de Jarník) est un algorithme glouton qui trouve un arbre couvrant minimum pour un graphe non orienté pondéré . Cela signifie qu'il trouve un sous-ensemble des arêtes qui forme un arbre qui inclut chaque sommet , où le poids total de toutes les arêtes de l'arbre est minimisé. L'algorithme fonctionne en construisant cet arbre un sommet à la fois, à partir d'un sommet de départ arbitraire, à chaque étape en ajoutant la connexion la moins chère possible de l'arbre à un autre sommet.

L'algorithme a été développé en 1930 par tchèque mathématicien Vojtěch Jarnik et redécouvert plus tard et réédité par des informaticiens Robert C. Prim en 1957 et Edsger Dijkstra en 1959. Par conséquent, il est aussi parfois appelé l' algorithme de Jarnik , algorithme Prim-Jarnik , Prim –Algorithme de Dijkstra ou l' algorithme DJP .

D' autres algorithmes bien connus pour ce problème comprennent l'algorithme de Kruskal et l'algorithme de Borůvka . Ces algorithmes trouvent la forêt couvrante minimale dans un graphe éventuellement déconnecté ; en revanche, la forme la plus basique de l'algorithme de Prim ne trouve que des arbres couvrants minimum dans les graphes connectés. Cependant, en exécutant l'algorithme de Prim séparément pour chaque composant connecté du graphique, il peut également être utilisé pour trouver la forêt couvrante minimale. En termes de complexité temporelle asymptotique , ces trois algorithmes sont également rapides pour les graphes clairsemés , mais plus lents que d'autres algorithmes plus sophistiqués. Cependant, pour les graphiques suffisamment denses, l'algorithme de Prim peut être exécuté en temps linéaire , respectant ou améliorant les limites de temps pour d'autres algorithmes.

Algorithme de Prim commençant au sommet A. Dans la troisième étape, les arêtes BD et AB ont toutes deux le poids 2, donc BD est choisi arbitrairement. Après cette étape, AB n'est plus un candidat pour l'ajout à l'arbre car il relie deux nœuds qui sont déjà dans l'arbre.

La description

L'algorithme peut être décrit de manière informelle comme effectuant les étapes suivantes :

Initialiser un arbre avec un seul sommet, choisi arbitrairement dans le graphe.
Agrandir l'arbre d'une arête : parmi les arêtes qui relient l'arbre aux sommets qui ne sont pas encore dans l'arbre, trouvez l'arête de poids minimum et transférez-la à l'arbre.
Répétez l'étape 2 (jusqu'à ce que tous les sommets soient dans l'arbre).

Plus en détail, il peut être implémenté en suivant le pseudocode ci-dessous.

Associez à chaque sommet v du graphe un nombre C [ v ] (le coût le moins cher d'une connexion à v ) et une arête E [ v ] (l'arête fournissant cette connexion la moins chère). Pour initialiser ces valeurs, définissez toutes les valeurs de C [ v ] sur +∞ (ou sur n'importe quel nombre supérieur au poids de bord maximal) et définissez chaque E [ v ] sur une valeur d' indicateur spéciale indiquant qu'il n'y a pas de bord reliant v à plus tôt sommets.
Initialiser une forêt vide F et un ensemble Q de sommets qui n'ont pas encore été inclus dans F (initialement, tous les sommets).
Répétez les étapes suivantes jusqu'à ce que Q soit vide :
1. Trouver et supprimer un sommet v de Q ayant la valeur minimale possible de C [ v ]
2. Ajoutez v à F et, si E [ v ] n'est pas la valeur du drapeau spécial, ajoutez également E [ v ] à F
3. Boucle sur les arêtes vw reliant v aux autres sommets w . Pour chacune de ces arêtes, si w appartient toujours à Q et que vw a un poids inférieur à C [ w ], procédez comme suit :
  1. Définir C [ w ] au coût du bord vw
  2. Réglez E [ w ] pour pointer vers le bord vw .
Retour F

Comme décrit ci-dessus, le sommet de départ de l'algorithme sera choisi arbitrairement, car la première itération de la boucle principale de l'algorithme aura un ensemble de sommets dans Q qui ont tous des poids égaux, et l'algorithme démarrera automatiquement un nouvel arbre dans F lorsqu'il complète un arbre couvrant de chaque composant connecté du graphe d'entrée. L'algorithme peut être modifié pour commencer avec n'importe quel sommet s particulier en définissant C [ s ] pour être un nombre plus petit que les autres valeurs de C (par exemple, zéro), et il peut être modifié pour ne trouver qu'un seul arbre couvrant plutôt que une forêt couvrante entière (correspondant plus étroitement à la description informelle) en s'arrêtant chaque fois qu'elle rencontre un autre sommet marqué comme n'ayant pas de bord associé.

Différentes variantes de l'algorithme diffèrent les unes des autres dans la façon dont l'ensemble Q est implémenté : comme une simple liste chaînée ou un tableau de sommets, ou comme une structure de données de file d'attente prioritaire plus compliquée . Ce choix conduit à des différences dans la complexité temporelle de l'algorithme. En général, une file d'attente prioritaire sera plus rapide pour trouver le sommet v avec un coût minimum, mais entraînera des mises à jour plus coûteuses lorsque la valeur de C [ w ] change.

Complexité temporelle

Lire les médias

L'algorithme de Prim a de nombreuses applications, comme dans la génération de ce labyrinthe, qui applique l'algorithme de Prim à un graphe de grille pondéré au hasard .

La complexité temporelle de l'algorithme de Prim dépend des structures de données utilisées pour le graphe et pour l'ordre des arêtes par poids, ce qui peut être fait en utilisant une file d'attente prioritaire . Le tableau suivant montre les choix typiques :

Structure de données de poids de bord minimum	Complexité temporelle (totale)
matrice de contiguïté , recherche	${\style d'affichage O(\|V\|^{2})}$
tas binaire et liste d'adjacence	$O((\|V\|+\|E\|)\log \|V\|)=O(\|E\|\log \|V\|)$
tas de Fibonacci et liste d'adjacence	${\style d'affichage O(\|E\|+\|V\|\log \|V\|)}$

Une implémentation simple de Prim, utilisant une matrice d'adjacence ou une représentation graphique de liste d'adjacence et recherchant linéairement un tableau de poids pour trouver le bord de poids minimum à ajouter, nécessite un temps d'exécution O (|V| ² ). Cependant, ce temps d'exécution peut être grandement amélioré en utilisant des tas pour implémenter la recherche de bords de poids minimum dans la boucle interne de l'algorithme.

Une première version améliorée utilise un tas pour stocker toutes les arêtes du graphe d'entrée, classées par leur poids. Cela conduit à un temps d'exécution dans le pire des cas O(|E| log |E|). Mais stocker des sommets au lieu d'arêtes peut encore l'améliorer. Le tas doit ordonner les sommets par le plus petit poids de bord qui les connecte à n'importe quel sommet dans l' arbre couvrant minimum partiellement construit (MST) (ou à l'infini si aucun tel bord n'existe). Chaque fois qu'un sommet v est choisi et ajouté au MST, une opération de touche de diminution est effectuée sur tous les sommets w en dehors du MST partiel de telle sorte que v soit connecté à w , en réglant la clé au minimum de sa valeur précédente et du coût du bord de ( v , w ).

En utilisant une simple structure de données de tas binaire , l'algorithme de Prim peut maintenant être exécuté dans le temps O (|E| log |V|) où |E| est le nombre d'arêtes et |V| est le nombre de sommets. En utilisant un tas de Fibonacci plus sophistiqué , cela peut être ramené à O (|E| + |V| log |V|), qui est asymptotiquement plus rapide lorsque le graphe est suffisamment dense pour que |E| est ω (|V|), et le temps linéaire lorsque |E| est au moins |V| log |V|. Pour les graphes de densité encore plus grande (ayant au moins |V| ^c arêtes pour certains c > 1), l'algorithme de Prim peut être exécuté en temps linéaire encore plus simplement, en utilisant un tas d -aire à la place d'un tas de Fibonacci.

Démonstration de preuve. Dans ce cas, le graphe Y ₁ = Y − f + e est déjà égal à Y . En général, le processus peut devoir être répété.

Preuve d'exactitude

Soit P un graphe connexe pondéré . À chaque itération de l'algorithme de Prim, une arête doit être trouvée qui relie un sommet dans un sous-graphe à un sommet à l'extérieur du sous-graphe. Puisque P est connecté, il y aura toujours un chemin vers chaque sommet. La sortie Y de l'algorithme de Prim est un arbre , car l'arête et le sommet ajoutés à l'arbre Y sont connectés. Soit Y ₁ un arbre couvrant minimum du graphe P. Si Y ₁ = Y alors Y est un arbre couvrant minimum. Sinon, soit e la première arête ajoutée lors de la construction de l'arbre Y qui n'est pas dans l'arbre Y ₁ , et V l'ensemble des sommets reliés par les arêtes ajoutées avant l'arête e . Alors une extrémité de l'arête e est dans l'ensemble V et l'autre ne l'est pas. Puisque l'arbre Y ₁ est un arbre couvrant du graphe P , il existe un chemin dans l'arbre Y ₁ joignant les deux extrémités. Au fur et à mesure que l'on se déplace le long du chemin, on doit rencontrer une arête f joignant un sommet de l'ensemble V à un autre qui n'est pas dans l'ensemble V . Maintenant, à l'itération où l'arête e a été ajoutée à l'arbre Y , l'arête f aurait également pu être ajoutée et elle serait ajoutée à la place de l'arête e si son poids était inférieur à e , et puisque l'arête f n'a pas été ajoutée, nous concluons que

{\style d'affichage w(f)\geq w(e).}

Soit l'arbre Y ₂ le graphe obtenu en enlevant l'arête f et en ajoutant l'arête e à l'arbre Y ₁ . Il est facile de montrer que l'arbre Y ₂ est connexe, a le même nombre d'arêtes que l'arbre Y ₁ et que le poids total de ses arêtes n'est pas supérieur à celui de l'arbre Y ₁ , c'est donc aussi un arbre couvrant minimum du graphe P et il contient l'arête e et toutes les arêtes ajoutées avant elle lors de la construction de l'ensemble V . Répétez les étapes ci-dessus et nous obtiendrons éventuellement un arbre couvrant minimum du graphe P identique à l'arbre Y . Cela montre que Y est un arbre couvrant minimum. L'arbre couvrant minimum permet d'étendre le premier sous-ensemble de la sous-région en un sous-ensemble plus petit X , que nous supposons être le minimum.

Algorithme parallèle

La matrice d'adjacence distribuée entre plusieurs processeurs pour l'algorithme de Prim parallèle. À chaque itération de l'algorithme, chaque processeur met à jour sa partie de C en inspectant la ligne du sommet nouvellement inséré dans son ensemble de colonnes dans la matrice d'adjacence. Les résultats sont ensuite collectés et le prochain sommet à inclure dans le MST est sélectionné globalement.

La boucle principale de l'algorithme de Prim est intrinsèquement séquentielle et donc non parallélisable . Cependant, la boucle interne , qui détermine la prochaine arête de poids minimum qui ne forme pas un cycle, peut être parallélisée en divisant les sommets et les arêtes entre les processeurs disponibles. Le pseudo-code suivant le démontre.

Affectez à chaque processeur un ensemble de sommets consécutifs de longueur . ${\style d'affichage P_{i}}$ ${\style d'affichage V_{i}}$ ${\style d'affichage {\tfrac {|V|}{|P|}}}$
Créez C, E, F et Q comme dans l' algorithme séquentiel et divisez C, E, ainsi que le graphe entre tous les processeurs de telle sorte que chaque processeur retienne les arêtes entrantes à son ensemble de sommets. Soit , désignons les parties de C , E stockées sur le processeur . ${\style d'affichage C_{i}}$ ${\style d'affichage E_{i}}$ ${\style d'affichage P_{i}}$
Répétez les étapes suivantes jusqu'à ce que Q soit vide :
1. Sur chaque processeur : trouvez le sommet ayant la valeur minimale dans [ ] (solution locale). $v_{i}$ ${\style d'affichage C_{i}}$ $v_{i}$
2. Min-réduire les solutions locales pour trouver le sommet v ayant la valeur minimale possible de C [ v ] (solution globale).
3. Diffusez le nœud sélectionné à chaque processeur.
4. Ajoutez v à F et, si E [ v ] n'est pas la valeur du drapeau spécial, ajoutez également E [ v ] à F .
5. Sur chaque processeur : mise à jour et comme dans l'algorithme séquentiel. ${\style d'affichage C_{i}}$ ${\style d'affichage E_{i}}$
Retour F

Cet algorithme peut généralement être implémenté sur des machines distribuées ainsi que sur des machines à mémoire partagée. Il a également été implémenté sur des unités de traitement graphique (GPU). Le temps d'exécution est , en supposant que les opérations de réduction et de diffusion puissent être effectuées en . Une variante de l'algorithme de Prim pour les machines à mémoire partagée, dans laquelle l'algorithme séquentiel de Prim est exécuté en parallèle, à partir de différents sommets, a également été explorée. Il convient cependant de noter qu'il existe des algorithmes plus sophistiqués pour résoudre le problème de l' arbre couvrant minimum distribué de manière plus efficace. $O({\tfrac {|V|^{2}}{|P|}})+O(|V|\log |P|)$ $O(\log |P|)$

Voir également

L'algorithme de Dijkstra , un algorithme très similaire pour le problème du plus court chemin
Les Greedoids offrent un moyen général de comprendre l'exactitude de l'algorithme de Prim

Les références

Liens externes

L'algorithme de Prim progresse sur des points distribués aléatoirement
Médias liés à l'algorithme de Prim sur Wikimedia Commons

Languages

In other projects