MST de Prim avec un tas
Faire croître l’arbre à partir d’un sommet
MST de Prim avec un tas est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 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.
Un autre chemin vers le MST
L'algorithme de Prim trouve lui aussi un arbre couvrant de poids minimal, mais il fait croître une seule zone connexe vers l'extérieur au lieu de trier d'abord toutes les arêtes. 🌱
Commencer par un sommet
Choisissez n'importe quel sommet de départ et marquez-le comme visité. L'arbre commence par un seul nœud et s'agrandit une arête à la fois.
visited = [False] * nL'idée de frontière
À chaque étape, examinez toutes les arêtes qui vont de l'arbre vers l'extérieur. Prim choisit toujours l'arête de frontière la moins chère.
Un tas choisit le minimum
Un tas-min permet de trouver rapidement l'arête de frontière la moins chère. Insérez les arêtes candidates dans le tas et extrayez-en le poids le plus petit à chaque tour.
import heapq
heap = [(0, start)]Extraire l'arête la moins chère
Extrayez la plus petite entrée du tas. Elle vous donne le poids et le prochain sommet qu'il est le moins coûteux d'ajouter à l'arbre en croissance.
w, u = heapq.heappop(heap)Ignorer les entrées obsolètes
Un sommet peut apparaître plusieurs fois dans le tas. Si vous en extrayez un qui est déjà visité, ignorez-le simplement et extrayez l'entrée suivante.
if visited[u]:
continueAjouter et étendre
Marquez le sommet extrait comme visité et ajoutez son poids au total. Ensuite, insérez chacune de ses arêtes sortantes dans le tas pour les étapes suivantes.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))Répéter jusqu'à ce que tout soit parcouru
Continuez à extraire et à étendre l'arbre jusqu'à ce que chaque sommet soit visité. Le total accumulé est alors le poids de l'arbre couvrant de poids minimal.
Le temps d'exécution
Chaque arête peut être insérée une fois et extraite une fois. Prim fondé sur un tas s'exécute donc en O(E log V), ce qui est comparable à Kruskal.
Prim contre Kruskal
Utilisez Prim sur des graphes denses avec une liste d'adjacence, et Kruskal lorsque vous disposez déjà d'une simple liste d'arêtes. Les deux produisent le même poids de MST.
Cela ressemble à Dijkstra
La boucle du tas ressemble à celle de Dijkstra, mais vous comparez les poids bruts des arêtes, et non les distances des chemins. Reconnaître ce schéma vous fait gagner du temps de programmation. ⚡
Vérification rapide
Rappelez-vous comment Prim choisit son arête suivante à chaque tour.
Récapitulatif
Vous avez construit un MST avec Prim : commencez n'importe où, utilisez un tas-min pour ajouter l'arête de frontière la moins chère et ignorez les visites obsolètes. Excellent travail ! 🎉
Questions Fréquemment Posées
La leçon « MST de Prim avec un tas » est-elle gratuite ?
Oui — le texte complet de « MST de Prim avec un tas » 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 « MST de Prim avec un tas » ?
Faire croître l’arbre à partir d’un sommet 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 4 sur 4.
Combien de temps prend la leçon « MST de Prim avec un tas » ?
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