Kruskals algoritm
Sortera kanterna, ta den kortaste, slut aldrig en slinga. Kruskals algoritm är kanske den enklaste giriga algoritm som finns, och ändå hittar den alltid det billigaste sättet att förbinda alla noder i en graf.
Idén
Ett minimalt uppspännande träd förbinder alla noder i en viktad graf med minsta möjliga totala kantlängd. Kruskals algoritm låter inte ett träd växa från en start. Den tittar på hela grafen på en gång, börjar med varje nod som en egen del och fortsätter att förena delar med den kortaste tillgängliga kanten tills bara en del återstår.
Steg för steg
Sortera kanterna från kortast till längst. Prova dem i den ordningen. Om en kants två ändar ligger i olika delar, lägg till den i trädet: de två delarna blir en. Om båda ändarna redan finns i samma del skulle kanten sluta en cykel, så hoppa över den. Med n noder är trädet klart efter n − 1 kanter, och de återstående kanterna behöver aldrig granskas.
Ett exempel
Ta kanterna A–B med längd 1, B–C 2, A–C 3, C–D 4 och B–D 5. Kruskal lägger till A–B och sedan B–C, som förenar C med delen A–B. Sedan kommer A–C, men A och C finns redan i en del, så den skulle sluta cykeln A–B–C och hoppas över. C–D ansluter D, och nu bildar alla fyra noderna ett träd med tre kanter och total längd 7. B–D, den längsta kanten, provas aldrig ens.
Union-find
Den enda svåra frågan Kruskals algoritm ställer är: finns de här två noderna redan i samma del? En union-find-struktur svarar på den. Varje del är ett litet träd av länkar som pekar mot en representant. Find följer länkarna till representanten; union hänger in den ena representanten under den andra. Vägkomprimering, som låter varje besökt nod peka direkt på representanten, och union efter storlek håller länkarna så korta att varje fråga tar nästan konstant tid.
Historia och hastighet
Joseph Kruskal publicerade algoritmen 1956, i en kort artikel i Proceedings of the American Mathematical Society. Sorteringen av kanterna är den långsammaste delen, så arbetet växer med E log E för E kanter. Om kanterna redan är sorterade, eller om deras längder är små heltal, är den nästan linjär.
Utforska den
Öppna appen och tryck på Steg. Kanterna som återstår att prova listas under grafen, kortast först. Varje kant som förenar två delar blir grön; varje kant som skulle sluta en cykel ritas streckad i rött. Se flera små delar växa i olika delar av grafen och smälta samman, och lägg märke till att de sista kanterna ofta aldrig provas.
Ofta ställda frågor
Varför sorterar Kruskals algoritm kanterna?
Så att varje kant den lägger till är den kortaste som fortfarande förenar två delar. Det giriga valet är alltid säkert tack vare snittegenskapen, och varje överhoppad kant är den längsta i cykeln den skulle sluta, så den behövs aldrig.
Vad är en struktur för disjunkta mängder?
Ett annat namn för union-find: en struktur som håller reda på en samling separata mängder, här delarna i den växande skogen, och snabbt kan säga vilken mängd ett element tillhör och slå ihop två mängder.
Fungerar Kruskals algoritm på en osammanhängande graf?
Ja. Den slutar helt enkelt med ett träd för varje sammanhängande del av grafen, en minimal uppspännande skog, eftersom ingen kant kan förena delar som inte hänger ihop.
Används Kruskals algoritm till något annat?
Om man stoppar den tidigt, innan de sista delarna smälter samman, delar den in noderna i kluster, vilket är single-linkage-klustring. Kör man den på ett rutnät med slumpmässiga kantlängder skapar den en labyrint.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova Kruskals algoritm