Worldlex Wiki 
En informatique , l'algorithme de Prim est un algorithme glouton qui trouve un arbre couvrant minimal pour un graphe non orienté pondéré . Cela signifie qu'il trouve un sous-ensemble d' 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, en ajoutant à chaque étape la connexion la moins chère possible de l'arbre à un autre sommet.
L'algorithme a été développé en 1930 par le mathématicien tchèque Vojtěch Jarník et plus tard redécouvert et réédité par les informaticiens Robert C. Prim en 1957 et Edsger W. Dijkstra en 1959. Par conséquent, il est également parfois appelé algorithme de Jarník , algorithme Prim–Jarník , algorithme Prim–Dijkstra ou algorithme DJP .
D'autres algorithmes bien connus pour ce problème incluent 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 minimaux dans des graphes connectés. Cependant, en exécutant l'algorithme de Prim séparément pour chaque composant connecté du graphe, il peut également être utilisé pour trouver la forêt couvrante minimale. En termes de complexité temporelle asymptotique , ces trois algorithmes sont tout aussi rapides pour les graphes clairsemés , mais plus lents que d'autres algorithmes plus sophistiqués. Cependant, pour les graphes 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.
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.
- Faire grandir l'arbre par 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 vers l'arbre.
- Répétez l’étape 2 (jusqu’à ce que tous les sommets soient dans l’arbre).
De manière plus détaillée, cela peut être implémenté en suivant le pseudo-code ci-dessous.
- Associez à chaque sommet v du graphe un nombre C [ v ] (le coût le plus bas 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 un nombre supérieur au poids d'arête maximal) et définissez chaque E [ v ] sur une valeur d'indicateur spéciale indiquant qu'il n'y a pas d'arête reliant v aux sommets précédents.
- 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 :
- Trouver et supprimer un sommet v de Q ayant la valeur minimale possible de C [ v ]
- Ajouter v à F
- Boucle sur les arêtes vw reliant v à d'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 :
- Définir C [ w ] au coût du bord vw
- Réglez E [ w ] pour pointer vers le bord vw .
- Renvoie F , qui inclut spécifiquement les arêtes correspondantes dans E
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 terminera un arbre couvrant de chaque composant connexe du graphe d'entrée. L'algorithme peut être modifié pour démarrer avec n'importe quel sommet particulier s en définissant C [ s ] comme étant un nombre inférieur aux autres valeurs de C (par exemple, zéro), et il peut être modifié pour ne trouver qu'un seul arbre couvrant plutôt qu'une forêt couvrante entière (correspondant plus étroitement à la description informelle) en s'arrêtant chaque fois qu'il rencontre un autre sommet marqué comme n'ayant aucune arête associée.
Les différentes variantes de l'algorithme diffèrent les unes des autres par la manière 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 complexe. 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
La complexité temporelle de l'algorithme de Prim dépend des structures de données utilisées pour le graphe et pour classer les arêtes par poids, ce qui peut être fait à l'aide d'une file d'attente prioritaire . Le tableau suivant montre les choix typiques :
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 l'arête de poids minimum à ajouter, nécessite un temps d'exécution de O (|V| 2 ). Cependant, ce temps d'exécution peut être grandement amélioré en utilisant des tas pour implémenter la recherche d'arêtes 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, ordonnées par leur poids. Cela conduit à un temps d'exécution dans le pire des cas de O(|E| log |E|). Mais le stockage des sommets au lieu des arêtes peut encore l'améliorer. Le tas doit ordonner les sommets selon le plus petit poids d'arête qui les relie à n'importe quel sommet dans l' arbre couvrant minimal (MST) partiellement construit (ou l'infini si aucune arête de ce type n'existe). Chaque fois qu'un sommet v est choisi et ajouté au MST, une opération de diminution de clé est effectuée sur tous les sommets w en dehors du MST partiel de telle sorte que v soit connecté à w , définissant la clé au minimum de sa valeur précédente et du coût d'arête de ( v , w ).
En utilisant une structure de données de tas binaire simple , l'algorithme de Prim peut maintenant être montré pour s'exécuter en 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| soit ω (|V|), et en temps linéaire lorsque |E| est au moins |V| log |V|. Pour des graphes de densité encore plus grande (ayant au moins |V| c arêtes pour un certain c > 1), l'algorithme de Prim peut être fait pour s'exécuter en temps linéaire encore plus simplement, en utilisant un tas d -aire à la place d'un tas de Fibonacci.
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 d'un sous-graphe à un sommet extérieur au sous-graphe. Puisque P est connexe, 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 1 un arbre couvrant minimal du graphe P. Si Y 1 = Y alors Y est un arbre couvrant minimal. 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 1 , et V l'ensemble des sommets connecté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 1 est un arbre couvrant du graphe P , il existe un chemin dans l'arbre Y 1 reliant les deux extrémités. En parcourant le chemin, on doit rencontrer une arête f reliant un sommet de l'ensemble V à un sommet 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 aurait été 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
Soit l'arbre Y 2 le graphe obtenu en supprimant l'arête f de l'arbre Y 1 et en y ajoutant l'arête e . Il est facile de montrer que l'arbre Y 2 est connexe, qu'il a le même nombre d'arêtes que l'arbre Y 1 et que le poids total de ses arêtes n'est pas supérieur à celui de l'arbre Y 1 . Par conséquent, il s'agit également d'un arbre couvrant minimal du graphe P et qu'il contient l'arête e et toutes les arêtes ajoutées avant lui lors de la construction de l'ensemble V . Répétez les étapes ci-dessus et nous obtiendrons finalement un arbre couvrant minimal du graphe P identique à l'arbre Y . Cela montre que Y est un arbre couvrant minimal. L'arbre couvrant minimal permet au premier sous-ensemble de la sous-région d'être étendu en un sous-ensemble plus grand X , que nous supposons être le minimum.
Algorithme parallèle
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 le prochain bord de poids minimum qui ne forme pas un cycle, peut être parallélisée en divisant les sommets et les bords entre les processeurs disponibles. Le pseudo-code suivant le démontre.
- Attribuez à chaque processeur un ensemble de sommets consécutifs de longueur .
- Créez C, E, F et Q comme dans l'algorithme séquentiel et divisez C, E, ainsi que le graphique entre tous les processeurs de telle sorte que chaque processeur conserve les arêtes entrantes vers son ensemble de sommets. Soit , les parties de C , E stockées sur le processeur .
- Répétez les étapes suivantes jusqu'à ce que Q soit vide :
- Sur chaque processeur : trouver le sommet ayant la valeur minimale dans [ ] (solution locale).
- Réduisez au minimum les solutions locales pour trouver le sommet v ayant la valeur minimale possible de C [ v ] (solution globale).
- Diffuser le nœud sélectionné à chaque processeur.
- Ajoutez v à F et, si E [ v ] n’est pas la valeur de l’indicateur spécial, ajoutez également E [ v ] à F .
- Sur chaque processeur : mise à jour et comme dans l'algorithme séquentiel.
- 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. Le temps d'exécution est de , en supposant que les opérations de réduction et de diffusion peuvent ê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.