Time and Space Complexity
Leçon 7 sur 9 du cours Algorithme de Prim - Algorithmes de graphes de Coddy.
Complexité temporelle :
- La version par balayage des arêtes ici est O(V * E) : V-1 itérations, chacune balayant toutes les E arêtes. Avec un tas binaire et des listes d'adjacence, Prim s'exécute en O((V + E) log V).
Complexité spatiale :
- O(V) pour le tableau
inTree(plus les arêtes d'entrée).
Résumé :
- Prim fait croître un seul arbre, en ajoutant toujours l'arête la moins chère qui en sort, jusqu'à ce que chaque sommet soit inclus.
- Il produit le même poids total minimum que Kruskal, en utilisant une stratégie différente.
Essayez vous-même
Cette leçon ne comprend pas de défi de code.
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Algorithme de Prim - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity