Implementation (Part 2)
Leçon 6 sur 9 du cours Algorithme de Prim - Algorithmes de graphes de Coddy.
Maintenant, développez l'arbre, en ajoutant toujours l'arête de traverse la moins coûteuse.
Défi
MoyenMaintenant, faites croître l'arbre entier.
Écrivez une fonction nommée prim qui prend n et le tableau plat edges (triplets, non orientés) d'un graphe connexe, et renvoie le poids total de l'Arbre Couvrant de Poids Minimum, en commençant l'arbre à partir du sommet 0.
Conservez un indicateur inTree par sommet. À chaque tour, trouvez l'arête la moins chère ayant exactement une extrémité dans l'arbre, ajoutez son poids et intégrez son extrémité extérieure dans l'arbre.
Essayez vous-même
#include <stdlib.h>
int prim(int n, int* edges, int edges_size) {
// Écrivez le code ici
return 0;
}
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