Différence entre Kruskal et Prim
Kruskal vs prim
En informatique, les algorithmes Prim's et Kruskal sont un algorithme gourmand qui trouve un arbre couvrant minimum pour un graphique non dirigée connecté. Un arbre couvrant est un sous-graphique d'un graphique tel que chaque nœud du graphique est connecté par un chemin, qui est un arbre. Chaque arbre couvrant a un poids, et le poids / coût minimum possible de tous les arbres couvrant 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 indiqué en trois étapes clés;
Étant donné le graphique connecté avec n nœuds et le poids respectif de chaque bord,
1. Sélectionnez un nœud arbitraire dans le graphique et ajoutez-le à l'arborescence T (qui sera le premier nœud)
2. Considérez les poids de chaque bord connectés aux nœuds de l'arbre et sélectionnez le minimum. Ajouter le bord et le nœud à l'autre extrémité de l'arbre T et retirer le bord du graphique. (Sélectionnez un si deux ou plusieurs minimums existent)
3. Répétez l'étape 2, jusqu'à ce que les arêtes N-1 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 graphique doit être un graphique connecté. La forme de base de l'algorithme du 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 graphique avec n nœuds et le poids respectif de chaque bord,
1. Sélectionnez l'arc avec le moindre poids de l'ensemble du graphique et ajoutez à l'arbre et supprimez du graphique.
2. Du reste sélectionnez le bord le moins pondéré, d'une manière qui ne forme pas un cycle. Ajoutez le bord à l'arbre et supprimez du graphique. (Sélectionnez un si deux ou plusieurs minimums existent)
3. Répétez le processus à l'étape 2.
Dans cette méthode, l'algorithme commence avec un bord le moins pondéré et continue de sélectionner chaque bord à chaque cycle. Par conséquent, dans l'algorithme, le graphique n'a pas besoin d'être connecté. L'algorithme de Kruskal a une complexité temporelle d'O (logv)
Quelle est la différence entre l'algorithme de Kruskal et Prim?
• L'algorithme de Prim s'initialise avec un nœud, tandis que l'algorithme de Kruskal s'installe avec un bord.
• Les algorithmes de Prim s'étendent d'un nœud à un autre tandis que l'algorithme de Kruskal sélectionne les bords d'une manière que la position du bord n'est pas basée sur la dernière étape.
• Dans l'algorithme de Prim, le graphique doit être un graphique connecté tandis que les Kruskal peuvent également fonctionner sur des graphiques déconnectés.
• L'algorithme de Prim a une complexité temporelle de O (V2), et la complexité temporelle de Kruskal est o (logv).
