Prims algoritm
Tänk dig att du drar kabel från ett kraftverk: först ansluter du den närmaste staden, sedan den stad som ligger närmast något som redan är anslutet, och så vidare. Det är Prims algoritm, och den slutar alltid med det billigaste möjliga nätet.
Idén
Ett minimalt uppspännande träd förbinder alla noder i en viktad graf med minsta möjliga totala kantlängd. Prims algoritm bygger det genom att låta ett träd växa utåt från en start. Trädet delas aldrig upp i bitar: i varje steg ansluter exakt en ny nod, via den kortaste kanten som leder ut ur trädet.
Steg för steg
Lägg starten i trädet. Spara för varje nod utanför trädet dess bästa kant: dess kortaste kant till någon nod i trädet. Upprepa sedan: välj den nod utanför trädet vars bästa kant är kortast, lägg till den i trädet med den kanten och titta på dess kanter. En granne utanför trädet som nu kan nås med en kortare kant får den kanten som sin nya bästa. Sluta när alla noder finns i trädet.
Ett exempel
Ta kanterna A–B med längd 1, B–C 2, A–C 3, C–D 4 och B–D 5, och börja i A. A:s kanter ger B bästa kanten 1 och C bästa kanten 3. B ligger närmast, så den ansluter via A–B; dess kanter förbättrar C till 2 och ger D 5. C ansluter via B–C, och dess kant C–D förbättrar D till 4. Till sist ansluter D via C–D. Trädet A–B, B–C, C–D har total längd 1 + 2 + 4 = 7.
Varför den är korrekt
I varje steg är noderna uppdelade i två grupper: de i trädet och de utanför. Snittegenskapen säger att den kortaste kanten mellan två sådana grupper alltid hör till något minimalt uppspännande träd. Prim lägger alltid till just den kanten, så trädet den har byggt hittills kan alltid byggas färdigt till ett minimalt uppspännande träd, och när alla noder har anslutit är det ett.
Historia och hastighet
Den tjeckiske matematikern Vojtěch Jarník publicerade algoritmen 1930. Robert Prim återupptäckte den på Bell Labs 1957, och Edsger Dijkstra igen 1959. Med de väntande noderna i en binär heap växer arbetet med E log V för V noder och E kanter; med en vanlig array är det ungefär V², vilket är bättre när nästan varje par av noder är förbundet. Med en Fibonacciheap är det E + V log V.
Utforska den
Öppna appen, klicka på en nod för att börja där och tryck på Steg. Noder i trädet är gröna, väntande noder blå, och varje väntande nods bästa kant ritas streckad. De väntande noderna listas under grafen med längden på sin bästa kant, kortast först: den första ansluter härnäst. Börja från olika noder och se ordningen ändras medan den totala längden förblir densamma.
Ofta ställda frågor
Vad är skillnaden mellan Prims och Dijkstras algoritm?
Båda låter ett område växa från en start med hjälp av en prioritetskö. Prim rangordnar en väntande nod efter längden på dess enda bästa kant till trädet; Dijkstra efter dess hela avstånd från starten. Prim ger ett minimalt uppspännande träd, Dijkstra ett träd av kortaste vägar.
Fungerar Prims algoritm med negativa kantlängder?
Ja. Till skillnad från Dijkstras algoritm jämför Prim bara kanter med varandra, så negativa längder ställer inte till något: den hittar ändå ett uppspännande träd med minsta summa.
Vad händer om grafen inte är sammanhängande?
Då stannar Prims algoritm när den har nått alla noder den kan: den ger bara ett minimalt uppspännande träd för startens del av grafen. Kör man den igen från en nod som inte har nåtts än får man en minimal uppspännande skog.
Är Prims eller Kruskals algoritm bäst?
Ingen av dem vinner alltid. Prim passar täta grafer och grafer som lagras som grannlistor; Kruskal passar glesa grafer som ges som en lista över kanter. Båda hittar ett träd med samma totala längd.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova Prims algoritm