Trädkanter
Total längd
Kontrollerade kanter

  • Aktuell
  • I trädet
  • Intill trädet
  • Bästa kant hittills

Mer om Prims algoritm

Prims algoritm

Prims algoritm bygger ett minimalt uppspännande träd, den billigaste uppsättningen kanter som förbinder alla noder, genom att låta ett enda träd växa från en start. I varje steg lägger den till den nod som kan nås med den kortaste kanten från trädet. Klicka på en nod för att börja där och stega igenom för att se de väntande noderna, deras bästa kanter och trädet växa. Tryck på Spela för att se trädet växa, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst. Klicka på en nod för att göra den till start: trädet växer därifrån. Talet på varje kant är dess längd. Under grafen finns noderna som väntar på att ansluta, var och en med längden på sin bästa kant till trädet, som ritas streckad. Ny graf skapar en annan graf; välj hur många noder och kanter den har. När brädet är markerat stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

Hur det fungerar

  1. Klicka på en nod för att göra den till start: trädet växer därifrån.
  2. Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst.
  3. Följ de väntande noderna under grafen, var och en med sin bästa kant till trädet. Ny graf skapar en annan graf att prova.

Så fungerar Prims algoritm

Börja med ett träd med en nod. Varje nod utanför trädet minns sin kortaste kant till trädet, om den har någon. Ta gång på gång den nod vars kant är kortast, lägg till den och kanten i trädet och titta på dess kanter: om någon är kortare än en grannes bästa kant hittills blir den grannens bästa kant. När alla noder har anslutit har trädet en kant färre än det finns noder, och dess totala längd är så liten som möjligt.

Prim och Dijkstra

Prims algoritm och Dijkstras algoritm ser nästan likadana ut: båda låter ett område växa från en start och håller de väntande noderna i en prioritetskö. Skillnaden är talet i kön. Dijkstra sparar varje nods hela avstånd från starten; Prim bara längden på dess enda bästa kant till trädet. Så Dijkstra bygger ett träd av kortaste vägar och Prim ett träd med minsta totala längd, och de två träden är ofta olika.

Ofta ställda frågor

Vad är Prims algoritm?

En girig algoritm som bygger ett minimalt uppspännande träd i en viktad graf genom att låta ett träd växa från en startnod och alltid lägga till den kortaste kanten som förbinder trädet med en nod utanför det.

Spelar startnoden någon roll?

Bara för ordningen: från vilken start som helst slutar Prims algoritm med ett uppspännande träd med samma minsta totala längd. När några kanter är lika långa kan själva trädet bli olika.

Vem uppfann Prims algoritm?

Vojtěch Jarník beskrev den först, 1930. Robert Prim återupptäckte den 1957 och Edsger Dijkstra 1959, så den kallas också Jarníks algoritm eller Prim–Jarníks algoritm.

Hur snabb är Prims algoritm?

Med en binär heap växer arbetet med E log V för V noder och E kanter. Med en enkel array i stället för en heap tar den ungefär V² steg, vilket är bättre för täta grafer där nästan varje par av noder är förbundet.

Skickas min graf någonstans?

Nej. Grafen skapas och trädet byggs i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Gå till Editor