Arbre couvrant minimal de Kruskal
Ajouter les arêtes les moins coûteuses sans créer de cycles
Arbre couvrant minimal de Kruskal est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce qu'un MST
Un arbre couvrant de poids minimal relie chaque sommet en utilisant le poids total minimal des arêtes, sans former de cycle. Imaginez le câblage d'une ville au moindre coût. 🌲
Idée fondamentale de Kruskal
L'algorithme de Kruskal applique une stratégie gloutonne : ajoutez sans cesse l'arête la moins chère qui ne crée pas de cycle, jusqu'à ce que tout le graphe soit relié.
Étape 1 : sort des arêtes
Commencez par appliquer sort à chaque arête, de la plus petite à la plus grande. La préférence gloutonne pour les arêtes bon marché permet d'obtenir un total final minimal.
edges.sort() # (weight, u, v)Pourquoi DSU convient parfaitement
L'ajout d'une arête forme un cycle uniquement si ses deux extrémités sont déjà reliées. DSU répond à ce test de connexité en un temps quasi constant. 🤝
Parcourir les arêtes triées
Parcourez les arêtes de la moins chère à la plus coûteuse. Pour chacune, vérifiez si ses deux extrémités partagent déjà une racine dans DSU.
for w, u, v in edges:
ru, rv = find(u), find(v)Accepter ou rejeter
Si les racines sont différentes, l'arête relie deux morceaux distincts : acceptez-la et réunissez-les. Si les racines sont identiques, ignorez-la pour éviter un cycle.
if ru != rv:
union(u, v)
total += wSavoir quand s'arrêter
Un arbre couvrant de n sommets possède exactement n moins 1 arêtes. Dès que vous en avez accepté autant, vous pouvez vous arrêter plus tôt.
Détecter la déconnexion
Si vous avez parcouru toutes les arêtes et en avez accepté moins de n moins 1, le graphe est déconnecté et aucun arbre couvrant n'existe.
Le coût en temps
Le tri domine le calcul : Kruskal s'exécute donc en O(E log E). Les opérations de DSU sont si rapides qu'elles augmentent à peine ce total.
Pourquoi la stratégie gloutonne est correcte
La propriété de coupe garantit que l'arête la plus légère traversant une séparation peut être ajoutée sans danger. C'est exactement pourquoi le choix de la moins chère ne mène jamais à une erreur.
Quand choisir Kruskal
Kruskal est particulièrement efficace sur les graphes peu denses fournis sous forme de liste d'arêtes, le format que les problèmes de concours vous donnent le plus souvent directement. ⚡
Vérification rapide
Déterminez ce qui indique à Kruskal de rejeter une arête.
Récapitulatif
Vous avez construit le MST de Kruskal : triez les arêtes, ajoutez la moins chère qui relie deux composantes via DSU, puis arrêtez-vous à n moins 1 arêtes. 🎉
Questions Fréquemment Posées
La leçon « Arbre couvrant minimal de Kruskal » est-elle gratuite ?
Oui — le texte complet de « Arbre couvrant minimal de Kruskal » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Arbre couvrant minimal de Kruskal » ?
Ajouter les arêtes les moins coûteuses sans créer de cycles Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Arbre couvrant minimal de Kruskal » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- DSU avec compression de chemin
- Union par rang et composantes
- Arbre couvrant minimal de Kruskal
- MST de Prim avec un tas