Kruskal contre Prim
En informatique, les algorithmes de Prim et de Kruskal sont un algorithme glouton qui trouve un arbre couvrant minimum pour un graphe non orienté pondéré connecté. Un arbre couvrant est un sous-graphe d'un graphe tel que chaque nœud du graphe est relié par un chemin, qui est un arbre. Chaque arbre couvrant a un poids, et le poids/coût minimum possible de tous les arbres couvrants est l'arbre couvrant minimum (MST).
En savoir plus sur l'algorithme de Prim
L'algorithme a été développé par le mathématicien tchèque Vojtěch Jarník en 1930 et plus tard indépendamment par l'informaticien Robert C. Prim en 1957. Il a été redécouvert par Edsger Dijkstra en 1959. L'algorithme peut être énoncé en trois étapes clés;
Étant donné le graphe connexe à n nœuds et le poids respectif de chaque arête, 1. Sélectionnez un nœud arbitraire dans le graphe et ajoutez-le à l'arbre T (qui sera le premier nœud)
2. Considérez les poids de chaque arête connectée aux nœuds de l'arbre et sélectionnez le minimum. Ajoutez l'arête et le nœud à l'autre extrémité de l'arbre T et supprimez l'arête du graphe. (Sélectionnez n'importe lequel si deux minimums ou plus existent)
3. Répétez l'étape 2, jusqu'à ce que n-1 arêtes soient ajoutées à l'arbre.
Dans cette méthode, l'arbre commence par un seul nœud arbitraire et se développe à partir de ce nœud à chaque cycle. Par conséquent, pour que l'algorithme fonctionne correctement, le graphe doit être un graphe connexe. La forme de base de l'algorithme de Prim a une complexité temporelle de O(V2).
En savoir plus sur l'algorithme de Kruskal
L'algorithme développé par Joseph Kruskal est apparu dans les actes de l'American Mathematical Society en 1956. L'algorithme de Kruskal peut également être exprimé en trois étapes simples.
Étant donné le graphe à n nœuds et le poids respectif de chaque arête, 1. Sélectionnez l'arc avec le moins de poids de tout le graphique et ajoutez-le à l'arbre et supprimez-le du graphique.
2. Parmi les autres, sélectionnez l'arête la moins pondérée, d'une manière qui ne forme pas de cycle. Ajoutez le bord à l'arbre et supprimez-le du graphique. (Sélectionnez n'importe lequel si deux minimums ou plus existent)
3. Répétez le processus à l'étape 2.
Dans cette méthode, l'algorithme commence par l'arête la moins pondérée et continue à sélectionner chaque arête à chaque cycle. Par conséquent, dans l'algorithme, le graphe n'a pas besoin d'être connecté. L'algorithme de Kruskal a une complexité temporelle de O(logV)
Quelle est la différence entre l'algorithme de Kruskal et celui de Prim ?
• L'algorithme de Prim s'initialise avec un nœud, alors que l'algorithme de Kruskal s'initialise avec un bord.
• Les algorithmes de Prim s'étendent d'un nœud à l'autre tandis que l'algorithme de Kruskal sélectionne les arêtes de manière à ce que la position de l'arête ne soit pas basée sur la dernière étape.
• Dans l'algorithme de prim, le graphe doit être un graphe connexe tandis que le Kruskal peut également fonctionner sur des graphes déconnectés.
• L'algorithme de Prim a une complexité temporelle de O(V2), et la complexité temporelle de Kruskal est O(logV).
