Différence entre Kruskal et Prim

Kruskal vs Prim

En informatique, les algorithmes de Prim et Kruskal sont un algorithme glouton qui trouve un arbre de recouvrement minimal pour un graphe connexe non orienté pondéré. Un arbre recouvrant est un sous-graphe d'un graphe tel que chaque nœud du graphe soit connecté par un chemin, qui est un arbre. Chaque arbre recouvrant a un poids, et le poids / coût minimum possible de tous les arbres couvrants est égal à l'arbre couvrant minimal (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, puis plus tard par l'informaticien Robert C. Prim en 1957. Il a été redécouvert par Edsger Dijkstra en 1959. Cet algorithme peut être défini en trois étapes clés;

Étant donné le graphe connecté avec n nœuds et le poids respectif de chaque arête,

1. Sélectionnez un noeud quelconque du graphe et ajoutez-le à l’arbre T (qui sera le premier noeud).

2. Prenez en compte les poids de chaque bord connecté aux noeuds de l’arborescence 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 graphique. (Choisissez s'il en existe deux ou plus)

3. Répétez l'étape 2 jusqu'à ce que n-1 arêtes soient ajoutées à l'arborescence..

Dans cette méthode, l'arborescence 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 de Prim a une complexité temporelle de O (V²).

En savoir plus sur l'algorithme de Kruskal

L'algorithme développé par Joseph Kruskal est apparu dans les procédures de l'American Mathematical Society en 1956. L'algorithme de Kruskal peut également être exprimé en trois étapes simples..

Étant donné le graphique à n nœuds et le poids respectif de chaque arête,

1. Sélectionnez l'arc avec le moins de poids du graphique entier et ajoutez-le à l'arbre et supprimez-le du graphique..

2. Sur le reste, sélectionnez le moins d'arête pondérée, de manière à ne pas former de cycle. Ajoutez le bord à l’arbre et supprimez-le du graphique. (Choisissez s'il en existe deux ou plus)

3. Répétez le processus à l'étape 2.

Dans cette méthode, l’algorithme commence par le bord le moins pondéré et continue à 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 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 commence avec un bord.

• Les algorithmes de Prim s'étendent d'un nœud à un 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 connecté, tandis que celui de Kruskal peut également fonctionner sur des graphes déconnectés..

• L'algorithme de Prim a une complexité temporelle de O (V²), et la complexité temporelle de Kruskal est O (logV).