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

Si nous arrêtons l'algorithme en milieu de l'algorithme de Prim, il génère toujours un arbre connecté, mais Kruskal, d'autre part, peut donner un arbre ou une forêt déconnectés

Answer 2

Utilisez les deux !, vérifiez simplement le cas possible.

Answer 3

Une application importante de l'algorithme de Kruskal est dans le regroupement de liens uniques.

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

Answer 4

Prim est meilleur pour les graphes plus denses, et dans ce cas, nous n'avons pas non plus à nous soucier beaucoup des cycles en ajoutant un arête, car nous nous occupons principalement des nœuds. Prim est plus rapide que Kruskal dans le cas des graphes complexes.

Answer 5

Performance ?

Si je me souviens bien, Kruskal est en moyenne plus efficace que Prim