Prims algoritme

Forestil dig, at du lægger kabel ud fra et kraftværk: du forbinder først den nærmeste by, så den by, der ligger tættest på noget, der allerede er forbundet, og så videre. Det er Prims algoritme, og den ender altid med det billigst mulige net.

En graf med et træ, der vokser fra én knude, de ventende knuder omkring det med deres bedste kanter stiplet, og de ventende knuder listet nedenunder
En graf med et træ, der vokser fra én knude, de ventende knuder omkring det med deres bedste kanter stiplet, og de ventende knuder listet nedenunder

Idéen

Et minimalt udspændende træ forbinder alle knuder i en vægtet graf med den mindst mulige samlede kantlængde. Prims algoritme bygger det ved at lade ét træ vokse udad fra en start. Træet deler sig aldrig i stykker: i hvert trin kommer præcis én ny knude med, via den korteste kant, der fører ud af træet.

Trin for trin

Sæt starten i træet. For hver knude uden for træet gemmes dens bedste kant: dens korteste kant til en knude i træet. Gentag så: vælg den knude uden for træet, hvis bedste kant er kortest, tilføj den til træet med den kant, og undersøg dens kanter. En nabo uden for træet, som nu kan nås ad en kortere kant, får den kant som sin nye bedste. Stop, når alle knuder er i træet.

Et eksempel

Tag kanterne A–B med længde 1, B–C 2, A–C 3, C–D 4 og B–D 5, og start i A. A's kanter giver B den bedste kant 1 og C den bedste kant 3. B er nærmest, så den kommer med via A–B; dens kanter forbedrer C til 2 og giver D 5. C kommer med via B–C, og dens kant C–D forbedrer D til 4. Til sidst kommer D med via C–D. Træet A–B, B–C, C–D har samlet længde 1 + 2 + 4 = 7.

Hvorfor den er korrekt

I hvert trin er knuderne delt i to grupper: dem i træet og dem uden for. Snitegenskaben siger, at den korteste kant mellem to sådanne grupper altid hører til et minimalt udspændende træ. Prim tilføjer altid netop den kant, så det træ, den har bygget indtil nu, kan altid gøres færdigt til et minimalt udspændende træ, og når alle knuder er kommet med, er det et.

Historie og hastighed

Den tjekkiske matematiker Vojtěch Jarník udgav algoritmen i 1930. Robert Prim genopdagede den hos Bell Labs i 1957, og Edsger Dijkstra igen i 1959. Med de ventende knuder i en binær hob vokser arbejdet med E log V for V knuder og E kanter; med et almindeligt array er det omkring V², hvilket er bedre, når næsten hvert par knuder er forbundet. Med en Fibonacci-hob er det E + V log V.

Udforsk den

Åbn appen, klik på en knude for at starte der, og tryk på Trin. Knuder i træet er grønne, ventende knuder blå, og hver ventende knudes bedste kant tegnes stiplet. De ventende knuder står under grafen med længden af deres bedste kant, kortest først: den første kommer med som den næste. Start fra forskellige knuder, og se rækkefølgen ændre sig, mens den samlede længde er den samme.

Ofte stillede spørgsmål

Hvad er forskellen på Prims og Dijkstras algoritme?

Begge lader et område vokse fra en start ved hjælp af en prioritetskø. Prim rangerer en ventende knude efter længden af dens ene bedste kant til træet; Dijkstra efter dens hele afstand fra starten. Prim giver et minimalt udspændende træ, Dijkstra et træ af korteste veje.

Virker Prims algoritme med negative kantlængder?

Ja. I modsætning til Dijkstras algoritme sammenligner Prim kun kanter med hinanden, så negative længder giver ingen problemer: den finder stadig et udspændende træ med den mindste sum.

Hvad hvis grafen ikke er sammenhængende?

Så stopper Prims algoritme, når den har nået alle de knuder, den kan: den giver kun et minimalt udspændende træ for startens del af grafen. Kører man den igen fra en knude, der endnu ikke er nået, får man en minimalt udspændende skov.

Er Prims eller Kruskals algoritme bedst?

Ingen af dem vinder altid. Prim passer til tætte grafer og grafer, der er gemt som nabolister; Kruskal passer til tynde grafer, der er givet som en liste over kanter. Begge finder et træ med samme samlede længde.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Prøv Prims algoritme