Implementation (Part 2)
Leçon 6 sur 9 du cours Algorithme de Kruskal - Algorithmes de graphes de Coddy.
Maintenant, ajoutez l'arête sûre la moins chère jusqu'à ce que le MST soit complet.
Défi
MoyenMaintenant, construisez l'arbre couvrant minimal (MST).
Écrivez une fonction nommée kruskal qui prend n et le tableau plat edges (triplets, non orientés) d'un graphe connexe, et retourne le poids total de son arbre couvrant minimal.
Prenez de manière répétée l'arête inutilisée la moins chère ; si ses extrémités sont dans des ensembles différents, unissez-les et ajoutez son poids ; sinon, ignorez-la.
Réutilisez l'idée de l'union-find de la leçon précédente.
Essayez vous-même
#include <stdlib.h>
int kruskal(int n, int* edges, int edges_size) {
// Écrire 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 Kruskal - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity