MST di Prim con un heap
Far crescere l’albero a partire da un vertice
MST di Prim con un heap è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Un percorso diverso verso l'MST
Anche l'algoritmo di Prim trova un albero ricoprente minimo, ma fa crescere verso l'esterno un'unica componente connessa invece di ordinare prima tutti gli archi. 🌱
Crescere a partire da un vertice
Si scelga un vertice iniziale qualsiasi e lo si contrassegni come visitato. L'albero inizia con un solo nodo e si espande un arco alla volta.
visited = [False] * nL'idea della frontiera
A ogni passo si considerano tutti gli archi che collegano l'albero all'esterno. Prim sceglie sempre il più economico tra questi archi di frontiera.
Un min-heap sceglie il minimo
Un min-heap rende rapida la ricerca dell'arco di frontiera più economico. A ogni iterazione si inseriscono gli archi candidati e si estrae quello con il peso minore.
import heapq
heap = [(0, start)]Estrarre l'arco più economico
Si estrae l'elemento più piccolo dall'heap. Esso fornisce il peso e il vertice successivo più economico da aggiungere all'albero in crescita.
w, u = heapq.heappop(heap)Ignorare gli elementi obsoleti
Un vertice può comparire più di una volta nell'heap. Se se ne estrae uno già visitato, lo si ignora e si estrae il successivo.
if visited[u]:
continueAggiungere ed espandere
Si contrassegna il vertice estratto come visitato e si aggiunge il suo peso al totale. Poi si inseriscono nell'heap tutti gli archi uscenti, per i passaggi successivi.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))Ripetere fino a completamento
Si continua a estrarre ed espandere finché ogni vertice non è stato visitato. A quel punto, il totale accumulato è il peso dell'albero ricoprente minimo.
Il tempo di esecuzione
Ogni arco può essere inserito una volta ed estratto una volta, quindi l'algoritmo di Prim basato su heap ha complessità O(E log V), paragonabile a quella di Kruskal.
Prim a confronto con Kruskal
Si usi Prim sui grafi densi con una lista di adiacenza e Kruskal quando si dispone già di una semplice lista di archi. Entrambi producono lo stesso peso dell'MST.
Sembra Dijkstra
Il ciclo sull'heap ricorda quello di Dijkstra, ma si confrontano i pesi grezzi degli archi, non le distanze dei percorsi. Riconoscere questo schema fa risparmiare tempo nella scrittura del codice. ⚡
Verifica rapida
Ricordi come Prim sceglie il prossimo arco a ogni iterazione.
Riepilogo
Ha costruito un MST con Prim: partire da un punto qualsiasi, usare un min-heap per aggiungere l'arco di frontiera più economico e ignorare le visite obsolete. Ottimo lavoro! 🎉
Domande Frequenti
La lezione «MST di Prim con un heap» è gratuita?
Sì — il testo completo di «MST di Prim con un heap» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «MST di Prim con un heap»?
Far crescere l’albero a partire da un vertice Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «MST di Prim con un heap»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- DSU con compressione dei cammini
- Union per rango e componenti
- Albero ricoprente minimo di Kruskal
- MST di Prim con un heap