Trädkanter
Total längd
Kontrollerade kanter

  • Aktuell
  • I trädet
  • Skulle sluta en cykel

Mer om Kruskals algoritm

Kruskals algoritm

Kruskals algoritm bygger ett minimalt uppspännande träd, den billigaste uppsättningen kanter som förbinder alla noder, på enklast tänkbara sätt: ta kanterna från kortast till längst och behåll varje kant, utom om den skulle sluta en cykel. Stega igenom för att se separata delar växa och smälta samman till ett träd, och kanterna som hoppas över. 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. Talet på varje kant är dess längd. Under grafen finns kanterna som återstår att prova, från kortast till längst; en kant vars ändar redan är förbundna skulle sluta en cykel och ritas streckad i rött. 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. Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget.
  2. Dra i stegreglaget för att hoppa var som helst. Kanterna som återstår att prova listas under grafen, kortast först.
  3. Håll utkik efter kanterna som är streckade i rött: de skulle sluta en cykel. Ny graf skapar en annan graf att prova.

Så fungerar Kruskals algoritm

Sortera alla kanter från kortast till längst. Börja med varje nod som en egen del. Prova kanterna i tur och ordning: om en kant förenar två olika delar läggs den i trädet och de två delarna blir en; om dess två ändar redan finns i samma del skulle den sluta en cykel, så hoppa över den. Sluta när allt är en enda del. Det sker efter en kant färre än det finns noder, ofta långt innan den sista kanten har provats.

Union-find

För varje kant måste Kruskals algoritm fråga om dess två ändar redan är förbundna. En union-find-struktur svarar snabbt på det: varje del har en representant, find följer länkarna till den, och union länkar den ena representanten till den andra. Med två enkla knep, vägkomprimering och union efter storlek, tar varje fråga nästan konstant tid, så sorteringen av kanterna är den långsammaste delen, med ett arbete som växer med E log E.

Ofta ställda frågor

Vad är Kruskals algoritm?

En girig algoritm som bygger ett minimalt uppspännande träd genom att sortera alla kanter från kortast till längst och lägga till varje kant som inte sluter en cykel med de kanter som redan är valda.

Hur upptäcker Kruskals algoritm en cykel?

En kant sluter en cykel precis när dess två ändar redan är förbundna av valda kanter. En union-find-struktur håller reda på vilka noder som är förbundna och svarar på den frågan nästan direkt.

Varför fungerar Kruskals algoritm?

Tack vare cykelegenskapen: den längsta kanten i en cykel behövs aldrig för ett minimalt uppspännande träd. Varje kant som Kruskal hoppar över är den längsta i cykeln den skulle sluta, eftersom alla kanter före den var kortare eller lika långa.

När ska jag använda Kruskal i stället för Prim?

Kruskals algoritm är enkel och snabb på glesa grafer och fungerar direkt på en vanlig lista över kanter. Prims algoritm passar täta grafer och grafer som lagras som grannlistor. Båda hittar ett träd med samma totala längd.

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