- Aktuel
- I træet
- Ved siden af træet
- Bedste kant indtil nu
Prims algoritme
Prims algoritme bygger et minimalt udspændende træ, det billigste sæt kanter, der forbinder alle knuder, ved at lade ét træ vokse fra en start. I hvert trin tilføjer den den knude, der kan nås ad den korteste kant fra træet. Klik på en knude for at starte der, og gå trin for trin for at se de ventende knuder, deres bedste kanter og træet vokse. Tryk på Afspil for at se træet vokse, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Klik på en knude for at gøre den til start: træet vokser derfra. Tallet på hver kant er dens længde. Under grafen står de knuder, der venter på at komme med, hver med længden af sin bedste kant til træet, som tegnes stiplet. Ny graf laver en anden graf; vælg, hvor mange knuder og kanter den har. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.
Sådan virker det
- Klik på en knude for at gøre den til start: træet vokser derfra.
- Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst.
- Hold øje med de ventende knuder under grafen, hver med sin bedste kant til træet. Ny graf laver en anden graf, du kan prøve.
Sådan virker Prims algoritme
Start med et træ med én knude. Hver knude uden for træet husker sin korteste kant til træet, hvis den har en. Tag igen og igen den knude, hvis kant er kortest, tilføj den og kanten til træet, og undersøg dens kanter: hvis en af dem er kortere end en nabos bedste kant indtil nu, bliver den naboens bedste kant. Når alle knuder er kommet med, har træet én kant færre, end der er knuder, og dets samlede længde er så lille som muligt.
Prim og Dijkstra
Prims algoritme og Dijkstras algoritme ligner næsten hinanden: begge lader et område vokse fra en start og holder de ventende knuder i en prioritetskø. Forskellen er tallet i køen. Dijkstra gemmer hver knudes hele afstand fra starten; Prim kun længden af dens ene bedste kant til træet. Så Dijkstra bygger et træ af korteste veje, og Prim et træ med den mindste samlede længde, og de to træer er ofte forskellige.
Ofte stillede spørgsmål
Hvad er Prims algoritme?
En grådig algoritme, der bygger et minimalt udspændende træ i en vægtet graf ved at lade ét træ vokse fra en startknude og altid tilføje den korteste kant, der forbinder træet med en knude uden for det.
Betyder startknuden noget?
Kun for rækkefølgen: fra enhver start ender Prims algoritme med et udspændende træ med den samme mindste samlede længde. Når nogle kanter er lige lange, kan selve træet være forskelligt.
Hvem opfandt Prims algoritme?
Vojtěch Jarník beskrev den først, i 1930. Robert Prim genopdagede den i 1957 og Edsger Dijkstra i 1959, så den kaldes også Jarníks algoritme eller Prim–Jarník-algoritmen.
Hvor hurtig er Prims algoritme?
Med en binær hob vokser arbejdet med E log V for V knuder og E kanter. Med et simpelt array i stedet for en hob tager den omkring V² trin, hvilket er bedre til tætte grafer, hvor næsten hvert par knuder er forbundet.
Bliver min graf sendt nogen steder hen?
Nej. Grafen laves, og træet bygges i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor