-4
Existe-t-il un meilleur algorithme (plus optimal, plus rapide) que Prime et Kruskal's algorithms?À propos du graphique Minimum Spanning Tree
A
Répondre
0
L'algorithme de Prime et les algorithmes de Kruskal fonctionnent très rapidement s'ils sont bien implémentés. Essayez d'utiliser des structures de données optimales pour votre cas de données. Dans vraiment vous n'avez pas besoin d'algorithme plus rapide dans la plupart des cas.
Si vous avez besoin d'une implémentation parallèle de l'algorithme, utilisez Borůvka's algorithm.
Si vous avez besoin de l'algorithme théorie-plus rapide, vérifiez l'algorithme Decision trees.
Et il y a un cas particulier avec linéaire algorithm.
+0
Quel est le meilleur pour un réseau complexe avec une très grande entrée? –
+0
Pour un graphique avec des arêtes V vertices E, l'algorithme de Kruskal s'exécute en temps O (E log V) et l'algorithme de Prim s'exécute en O (E + V log V) temps amorti. Donc, comptez E, V et décidez que c'est mieux. S'il y a beaucoup de vertex, mais pas beaucoup de bords, utilisez Prim's. S'il y a beaucoup plus de vertex, utilisez Kruskal. Et utilisez (ou écrivez) une bonne implémentation de cet algorithme, car une constante est très importante et une mauvaise implémentation peut être très lente. Si l'entrée est vraiment grande et que vous avez Xeon avec 12 cœurs (ou cluster avec de nombreuses instances), essayez d'utiliser l'algorithme de Boruvka. – knst
https://en.wikipedia.org/wiki/Minimum_spanning_tree#Faster_algorithms – DAle