Quand devrais-je utiliser Kruskal par opposition à Prim (et vice versa)?

Je me demandais quand on devrait utiliser l'algorithme de Prim et quand Kruskal pour trouver l'arbre couvrant minimum? Ils ont tous deux une logique simple, les mêmes pires cas, et la seule différence est la mise en œuvre qui peut impliquer des structures de données un peu différentes. Alors, quel est le facteur décisif?

Utilisez l'algorithme de Prim lorsque vous avez un graphique avec beaucoup d'arêtes.

Pour un graphe avec V sommets E bords, l'algorithme de Kruskal s'exécute en temps O (E log V) et l'algorithme de Prim peut s'exécuter en temps amorti O (E + V log V) , si vous utilisez un tas de Fibonacci .

L'algorithme de Prim est nettement plus rapide dans la limite lorsque vous avez un graphe vraiment dense avec beaucoup plus d'arêtes que de sommets. Kruskal fonctionne mieux dans les situations typiques (graphiques épars) car il utilise des structures de données plus simples.

J'ai trouvé un très joli fil sur le net qui explique la différence de manière très simple: http://www.thestudentroom.co.uk/showthread.php?t=232168 .

L'algorithme de Kruskal développera une solution à partir du bord le moins cher en ajoutant le prochain bord le moins cher, à condition qu'il ne crée pas de cycle.

L'algorithme de Prim fera croître une solution à partir d'un sommet aléatoire en ajoutant le prochain sommet le moins cher, le sommet qui n'est pas actuellement dans la solution mais qui lui est connecté par l'arête la moins chère.

Ci-joint une feuille intéressante sur ce sujet.

Si vous implémentez à la fois Kruskal et Prim, sous leur forme optimale: avec une recherche d'union et un tas de finbonacci respectivement, vous remarquerez à quel point Kruskal est facile à implémenter par rapport à Prim.

Prim est plus difficile avec un tas de fibonacci principalement parce que vous devez maintenir une table de comptabilité pour enregistrer le lien bidirectionnel entre les nœuds du graphe et les nœuds du tas. Avec une Union Find, c'est le contraire, la structure est simple et peut même produire directement le mst sans frais supplémentaires.

Je sais que vous ne l'avez pas demandé, mais si vous avez plus d'unités de traitement, vous devriez toujours considérer l'algorithme de Borůvka , car il pourrait être facilement parallélisé - il a donc un avantage de performance par rapport à l'algorithme de Kruskal et Jarník-Prim.

Kruskal peut avoir de meilleures performances si les arêtes peuvent être triées en temps linéaire ou sont déjà triées.

Prim est meilleur si le nombre d'arêtes aux sommets est élevé.

Le pire des cas de complexité temporelle de Kruskal est O (E log E) , car nous devons trier les arêtes. Le pire des cas de complexité temporelle Prim est O (E log V) avec file d'attente prioritaire ou mieux encore, O (E + V log V) avec Fibonacci Heap . Nous devrions utiliser Kruskal lorsque le graphe est clairsemé, avec un petit nombre d'arêtes, comme E = O (V), lorsque les arêtes sont déjà triées ou si nous pouvons les trier en temps linéaire. Nous devrions utiliser Prim lorsque le graphe est dense, c'est-à-dire que le nombre d'arêtes est élevé, comme E = O (V²).

Si nous arrêtons l'algorithme au milieu, l'algorithme de prim génère toujours un arbre connecté, mais kruskal d'un autre côté peut donner un arbre ou une forêt déconnecté

Une application importante de l'algorithme de Kruskal est le clustering à liaison unique .

Considérez n sommets et vous avez un graphe complet.Pour obtenir un k clusters de ces n points, exécutez l'algorithme de Kruskal sur les n- (k-1) premiers arêtes de l'ensemble trié d'arêtes.Vous obtenez k-cluster du graphe avec un maximum espacement.

Le meilleur moment pour Kruskal est O (E logV). Pour Prim utilisant des tas de fibres, nous pouvons obtenir O (E + V lgV). Par conséquent, sur un graphe dense, celui de Prim est bien meilleur.

Prim's est meilleur pour les graphes plus denses, et en cela nous n'avons pas non plus à prêter beaucoup d'attention aux cycles en ajoutant une arête, car nous avons principalement affaire à des nœuds. Prim est plus rapide que Kruskal dans le cas des graphes complexes.

Dans l'algorithme de kruskal, nous avons le nombre d'arêtes et le nombre de sommets sur un graphe donné, mais sur chaque arête, nous avons une valeur ou un poids pour lequel nous pouvons préparer un nouveau graphe qui ne doit pas être cyclique ou ne se fermer d'aucun côté Par exemple

graphique comme celui-ci _____________ | | | | | | | __________ | | Donnez un nom à n'importe quel sommet a, b, c, d, e, f.