Prims MST med en heap
Bygg treet ut fra ett toppunkt
Prims MST med en heap er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
En annen vei til MST-et
Prims algoritme finner også et minimumspennende tre, men den bygger ut én sammenhengende del utover i stedet for å sortere alle kantene først. 🌱
Start fra ett toppunkt
Velg et hvilket som helst starttoppunkt og marker det som besøkt. Treet begynner som én enkelt node og utvides med én kant om gangen.
visited = [False] * nFrontidéen
Ved hvert steg ser du på alle kanter som går fra treet til utsiden. Prim velger alltid den billigste av disse grensekantene.
En heap velger minimumet
En min-heap gjør det raskt å finne den billigste grensekanten. Du legger kandidatkanter inn i heapen og tar ut kanten med lavest vekt i hver runde.
import heapq
heap = [(0, start)]Ta ut den billigste kanten
Ta ut den minste oppføringen fra heapen. Den gir deg vekten og det neste toppunktet som billigst kan kobles til treet som vokser.
w, u = heapq.heappop(heap)Hopp over foreldede oppføringer
Et toppunkt kan ligge i heapen flere ganger. Hvis du tar ut et toppunkt som allerede er besøkt, ignorerer du det og tar ut neste oppføring.
if visited[u]:
continueLegg til og utvid
Marker toppunktet du tok ut, som besøkt, og legg vekten til totalen. Legg deretter alle de utgående kantene i heapen for senere steg.
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))Gjenta til alt er med
Fortsett å ta ut oppføringer og utvide til hvert toppunkt er besøkt. Da er den akkumulerte totalen vekten til det minimumspennende treet.
Kjøretiden
Hver kant kan legges inn én gang og tas ut én gang, så heap-basert Prim kjører på O(E log V), som er sammenlignbart med Kruskal.
Prim mot Kruskal
Bruk Prim på tette grafer med en naboliste, og Kruskal når du allerede har en enkel kantliste. Begge gir samme MST-vekt.
Det ligner på Dijkstra
Heap-løkken speiler Dijkstras, men du sammenligner rå kantvekter, ikke avstandsverdier for stier. Når du kjenner igjen mønsteret, sparer du tid på kodingen. ⚡
Rask sjekk
Husk hvordan Prim velger den neste kanten i hver runde.
Oppsummering
Du bygde et MST med Prim: start hvor som helst, bruk en min-heap for å legge til den billigste grensekanten, og hopp over foreldede besøk. Godt jobbet! 🎉
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Prims MST med en heap» gratis?
Ja – hele teksten i «Prims MST med en heap» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Prims MST med en heap»?
Bygg treet ut fra ett toppunkt Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Prims MST med en heap»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- DSU med banekomprimering
- Union by Rank og komponenter
- Kruskal og minimalt spennende tre
- Prims MST med en heap