Quand dois-je utiliser Kruskal par rapport à Prim (et vice versa) ?

Question

Je me demandais quand on devrait utiliser l'algorithme de Prim et quand celui de Kruskal pour trouver l'arbre couvrant minimal ? Ils ont tous les deux des logiques simples, les mêmes pires cas, et la seule différence est l'implémentation qui peut impliquer des structures de données un peu différentes. Alors, quel est le facteur décisif ?

Answer 1

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

Pour un graphe avec V sommets et E arêtes, 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 significativement plus rapide dans la limite lorsque vous avez un graphe très dense avec beaucoup plus d'arêtes que de sommets. Kruskal fonctionne mieux dans des situations typiques (graphe clairsemé) car il utilise des structures de données plus simples.

Answer 2

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 par rapport aux sommets est élevé.

Answer 3

Je sais que vous n'avez pas demandé cela, mais si vous avez plus d'unités de traitement, vous devriez toujours envisager l'algorithme de Borůvka, car il peut être facilement parallélisé - ce qui lui confère un avantage de performance par rapport à l'algorithme de Kruskal et de Jarník-Prim.

Answer 4

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

Answer 5

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

L'algorithme de Kruskal fera croître une solution à partir de l'arête la moins chère en ajoutant l'arête suivante la moins chère, à condition qu'elle 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 y est connecté par l'arête la moins chère.

Voici une feuille intéressante sur ce sujet.

Si vous implémentez à la fois Kruskal et Prim, dans leur forme optimale : avec une union find et un tas de Fibonacci respectivement, alors 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 suivi pour enregistrer le lien bidirectionnel entre les nœuds du graphe et les nœuds du tas. Avec une Union Find, c'est l'inverse, la structure est simple et peut même produire directement l'arbre couvrant minimum (ACM) avec un coût presque nul.