Albero ricoprente minimo di Kruskal
Aggiungere gli archi meno costosi senza creare cicli
Albero ricoprente minimo di Kruskal è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 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.
Che cos'è un MST
Un albero ricoprente minimo collega ogni vertice usando il peso totale minimo degli archi, senza creare cicli. È come cablare una città al minor costo possibile. 🌲
Idea centrale di Kruskal
L'algoritmo di Kruskal segue una strategia puramente greedy: continua ad aggiungere l'arco più economico che non crea un ciclo, finché l'intero grafo non è connesso.
Passo uno: ordinare gli archi
Per prima cosa, ordini ogni arco in base al peso, dal più piccolo al più grande. Preferire avidamente gli archi economici è ciò che rende minimo il totale finale.
edges.sort() # (weight, u, v)Perché DSU è perfetto
L'aggiunta di un arco crea un ciclo solo se i suoi due estremi sono già connessi. DSU verifica questa connettività in tempo quasi costante. 🤝
Esaminare gli archi ordinati
Esamina gli archi dal più economico al più costoso. Per ciascuno, verifica se i suoi due estremi condividono già una radice nella DSU.
for w, u, v in edges:
ru, rv = find(u), find(v)Accettare o rifiutare
Se le radici sono diverse, l'arco collega due componenti separate: lo si accetta e si esegue union su di esse. Se le radici coincidono, lo si salta per evitare un ciclo.
if ru != rv:
union(u, v)
total += wSapere quando fermarsi
Un albero ricoprente di n vertici ha esattamente n meno 1 archi. Dopo averne accettati così tanti, è possibile fermarsi in anticipo.
Rilevare la disconnessione
Se si esaminano tutti gli archi accettandone meno di n meno 1, il grafo è sconnesso e non esiste alcun albero ricoprente.
Il costo temporale
Il fattore dominante è l'ordinamento, quindi l'algoritmo di Kruskal ha complessità O(E log E). Le operazioni DSU sono così economiche da incidere appena sul totale.
Perché la strategia greedy è corretta
La proprietà dei tagli garantisce che l'arco di peso minimo che attraversa una qualsiasi divisione sia sicuro da aggiungere. Ecco perché scegliere prima gli archi più economici non porta mai a un risultato errato.
Quando scegliere Kruskal
L'algoritmo di Kruskal dà il meglio con i grafi sparsi rappresentati come liste di archi, il formato che la maggior parte dei problemi di programmazione competitiva fornisce direttamente. ⚡
Verifica rapida
Stabilisca che cosa induce Kruskal a rifiutare un arco.
Riepilogo
Ha costruito l'MST di Kruskal: ordinare gli archi, aggiungere il più economico che collega due componenti tramite DSU e fermarsi dopo n meno 1 archi. 🎉
Impara Coding Interview Prep con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 90
- Lezioni
- 360
Domande Frequenti
La lezione «Albero ricoprente minimo di Kruskal» è gratuita?
Sì — il testo completo di «Albero ricoprente minimo di Kruskal» è 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 «Albero ricoprente minimo di Kruskal»?
Aggiungere gli archi meno costosi senza creare cicli 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 3 di 4.
Quanto tempo richiede la lezione «Albero ricoprente minimo di Kruskal»?
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