Kruskals algoritme
Sortér kanterne, tag den korteste, luk aldrig en løkke. Kruskals algoritme er måske den enkleste grådige algoritme, der findes, og alligevel finder den altid den billigste måde at forbinde alle knuder i en graf på.
Idéen
Et minimalt udspændende træ forbinder alle knuder i en vægtet graf med den mindst mulige samlede kantlængde. Kruskals algoritme lader ikke ét træ vokse fra en start. Den ser på hele grafen på én gang, starter med hver knude som sit eget stykke og bliver ved med at forbinde stykker med den korteste ledige kant, indtil der kun er ét stykke tilbage.
Trin for trin
Sortér kanterne fra kortest til længst. Prøv dem i den rækkefølge. Hvis en kants to ender ligger i forskellige stykker, så tilføj den til træet: de to stykker bliver ét. Hvis begge ender allerede er i samme stykke, ville kanten lukke en kreds, så spring den over. Med n knuder er træet færdigt efter n − 1 kanter, og de resterende kanter behøver man aldrig se på.
Et eksempel
Tag kanterne A–B med længde 1, B–C 2, A–C 3, C–D 4 og B–D 5. Kruskal tilføjer A–B og så B–C, som forbinder C med stykket A–B. Så kommer A–C, men A og C er allerede i ét stykke, så den ville lukke kredsen A–B–C og springes over. C–D får D med, og nu danner alle fire knuder ét træ med tre kanter og samlet længde 7. B–D, den længste kant, bliver slet ikke prøvet.
Union-find
Det eneste svære spørgsmål, Kruskals algoritme stiller, er: er de to knuder allerede i samme stykke? En union-find-struktur svarer på det. Hvert stykke er et lille træ af henvisninger, der peger mod en repræsentant. Find følger henvisningerne til repræsentanten; union hænger den ene repræsentant ind under den anden. Stikomprimering, som får hver besøgt knude til at pege direkte på repræsentanten, og forening efter størrelse holder henvisningerne så korte, at hvert spørgsmål tager næsten konstant tid.
Historie og hastighed
Joseph Kruskal udgav algoritmen i 1956 i en kort artikel i Proceedings of the American Mathematical Society. Sorteringen af kanterne er den langsomste del, så arbejdet vokser med E log E for E kanter. Hvis kanterne allerede er sorteret, eller deres længder er små heltal, er den næsten lineær.
Udforsk den
Åbn appen, og tryk på Trin. De kanter, der endnu skal prøves, står under grafen, kortest først. Hver kant, der forbinder to stykker, bliver grøn; hver kant, der ville lukke en kreds, tegnes stiplet med rødt. Se flere små stykker vokse i forskellige dele af grafen og smelte sammen, og læg mærke til, at de sidste kanter ofte aldrig bliver prøvet.
Ofte stillede spørgsmål
Hvorfor sorterer Kruskals algoritme kanterne?
Så hver kant, den tilføjer, er den korteste, der stadig forbinder to stykker. Det grådige valg er altid sikkert på grund af snitegenskaben, og hver kant, der springes over, er den længste i den kreds, den ville lukke, så den er aldrig nødvendig.
Hvad er en struktur for disjunkte mængder?
Et andet navn for union-find: en struktur, der holder styr på en samling adskilte mængder, her stykkerne i den voksende skov, og hurtigt kan sige, hvilken mængde et element hører til, og slå to mængder sammen.
Virker Kruskals algoritme på en usammenhængende graf?
Ja. Den ender bare med ét træ for hver sammenhængende del af grafen, en minimalt udspændende skov, fordi ingen kant kan forbinde dele, der ikke hænger sammen.
Bruges Kruskals algoritme til andet?
Stopper man den tidligt, før de sidste stykker smelter sammen, deler den knuderne op i klynger, hvilket er single-linkage-klyngedannelse. Kører man den på et gitter med tilfældige kantlængder, laver den en labyrint.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv Kruskals algoritme