Kruskals algoritme - Kruskal's algorithm

Kruskals algoritme finner et minimum av skog i en ikke - rettet kantvektet graf . Hvis grafen er koblet til , finner den et minimum spennende tre . (Et minimum spennende tre i en tilkoblet graf er en delmengde av kantene som danner et tre som inkluderer hvert toppunkt , hvor summen av vekten av alle kantene i treet minimeres. For en frakoblet graf er et minimum spennende skog sammensatt av et minimumspennende tre for hver tilkoblet komponent .) Det er en grådig algoritme i grafteori, da den i hvert trinn legger til den neste laveste vektkanten som ikke vil danne en syklus til minimumspennskogen.

Denne algoritmen dukket først opp i Proceedings of the American Mathematical Society , s. 48–50 i 1956, og ble skrevet av Joseph Kruskal .

Andre algoritmer for dette problemet inkluderer Prims algoritme , omvendt slettingsalgoritme og Borůvkas algoritme .

Algoritme

• lage en skog F (et sett med trær), der hvert toppunkt i grafen er et eget tre
• lage et sett S som inneholder alle kantene i grafen
• mens S er ikketom og F er ennå ikke strekker seg
  • fjern en kant med minimum vekt fra S
  • Hvis den fjernede kanten forbinder to forskjellige trær, legg den til i skogen F og kombinerer to trær til et enkelt tre

Ved avslutningen av algoritmen danner skogen et minimum som spenner over skogen i grafen. Hvis grafen er koblet til, har skogen en enkelt komponent og danner et minimumstreet.

Pseudokode

En demo for Kruskals algoritme på en komplett graf med vekter basert på euklidisk avstand.

Følgende kode er implementert med en usammenhengende datastruktur . Her representerer vi vår skog F som et sett med kanter, og bruker den usammenhengende datastrukturen for effektivt å bestemme om to hjørner er en del av samme tre.

algorithm Kruskal(G) is
    F:= ∅
    for each v ∈ G.V do
        MAKE-SET(v)
    for each (u, v) in G.E ordered by weight(u, v), increasing do
        if FIND-SET(u) ≠ FIND-SET(v) then
            F:= F ∪ {(u, v)} ∪ {(v, u)}
            UNION(FIND-SET(u), FIND-SET(v))
    return F

Kompleksitet

For en graf med E- kanter og V- hjørner kan Kruskals algoritme vises å kjøre i O ( E log E ) tid, eller tilsvarende, O ( E log V ) tid, alt med enkle datastrukturer. Disse kjøretidene er ekvivalente fordi:

• E er på det meste og . ${\ displaystyle V ^ {2}}$${\ displaystyle \ log V ^ {2} = 2 \ log V \ i O (\ log V)}$
• Hvert isolerte toppunkt er en egen komponent i den minste skog. Hvis vi ignorerer isolerte hjørner får vi V ≤ 2 E , så logg V er . ${\ displaystyle O (\ log E)}$

Vi kan oppnå denne grensen som følger: Først sorterer du kantene etter vekt ved hjelp av en sammenligningssortering i O ( E log E ) tid; dette gjør at trinnet "fjerne en kant med minimum vekt fra S " kan fungere i konstant tid. Deretter bruker vi en usammenhengende datastruktur for å holde rede på hvilke hjørner som er i hvilke komponenter. Vi plasserer hvert toppunkt i sitt eget usammenhengende sett, som tar O ( V ) -operasjoner. Til slutt, i verste fall, må vi gjenta gjennom alle kanter, og for hver kant må vi gjøre to "finne" operasjoner og muligens en union. Selv en enkel usammenhengende datastruktur, som for eksempel usammenhengende skoger med forening etter rang, kan utføre O ( E ) -operasjoner i O ( E log V ) -tid. Dermed er den totale tiden O ( E log E ) = O ( E log V ).

Forutsatt at kantene enten allerede er sortert eller kan sorteres i lineær tid (for eksempel med tellesortering eller radiksortering ), kan algoritmen bruke en mer sofistikert usammenhengende datastruktur for å kjøre i O ( E α ( V )) tid , hvor α er den ekstremt langsomt voksende inversen av den enkeltverdige Ackermann-funksjonen .

Eksempel

Bilde	Beskrivelse
	AD og CE er de korteste kantene, med lengde 5, og AD er valgt vilkårlig , så det er uthevet.
	CE er nå den korteste kanten som ikke danner en syklus, med lengde 5, så den er uthevet som den andre kanten.
	Neste kant, DF med lengde 6, er uthevet ved å bruke omtrent samme metode.
	De nest korteste kantene er AB og BE , begge med lengde 7. AB velges vilkårlig og er uthevet. Kanten BD er uthevet i rødt, fordi det allerede eksisterer en sti (i grønt) mellom B og D , så det ville danne en syklus ( ABD ) hvis den ble valgt.
	Prosessen fortsetter å markere den neste minste kanten, BE med lengde 7. Mange flere kanter er fremhevet i rødt på dette stadiet: BC fordi det ville danne løkken BCE , DE fordi den ville danne løkken DEBA , og FE fordi den ville form FEBAD .
	Til slutt avsluttes prosessen med kanten EG på lengde 9, og det minste spennende treet blir funnet.

Bevis på korrekthet

Beviset består av to deler. For det første er det bevist at algoritmen produserer et spennende tre . For det andre er det bevist at det konstruerte spennende treet har minimal vekt.

Spennende tre

La være en sammenhengende, vektet graf og la være undergrafen til produsert av algoritmen. kan ikke ha en syklus, ettersom per definisjon ikke blir lagt til en kant hvis den resulterer i en syklus. kan ikke kobles fra, siden den første oppdagede kanten som går sammen med to komponenter av ville blitt lagt til av algoritmen. Dermed er et spennende tre av . ${\ displaystyle G}$${\ displaystyle Y}$${\ displaystyle G}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle Y}$${\ displaystyle G}$

Minimalitet

Vi viser at følgende proposisjon P er sant ved induksjon : Hvis F er det settet med kanter som er valgt på et hvilket som helst trinn i algoritmen, så er det noe minimumsomspennende tre som inneholder F og ingen av kantene avvist av algoritmen.

• Det er klart at P er sant i begynnelsen, når F er tom: ethvert minimum spennende tre vil gjøre, og det eksisterer et fordi en vektet koblet graf alltid har et minimum spennende tre.
• Anta nå P er tilfelle for noen ikke-avsluttende kant set F og la t være et minimum som strekker seg over tre som inneholder F .
  • Hvis den neste valgte kanten e også er i T , er P sant for F + e .
  • Ellers, hvis e ikke er i T deretter T + e har en syklus C . Denne syklusen inneholder kanter som ikke hører til F , ettersom e ikke danner en syklus når det tilsettes til F , men gjør på T . La f være en kant som er i C, men ikke i F + e . Merk at f også tilhører T , og av P har ikke blitt vurdert av algoritmen. f må derfor ha en vekt som er minst like stor som e . Deretter T - f + e er et tre, og den har samme eller mindre vekt som T . Så T - f + e er et minimum spennende tre som inneholder F + e og igjen holder P.
• Derfor, ved prinsippet om induksjon, holder P når F har blitt et spennende tre, noe som bare er mulig hvis F er et minimum av spennende tre i seg selv.

Parallell algoritme

Kruskals algoritme er iboende sekvensiell og vanskelig å parallellisere. Det er imidlertid mulig å utføre den innledende sorteringen av kantene parallelt, eller alternativt å bruke en parallell implementering av en binær haug for å trekke ut minimumsvektkanten i hver iterasjon. Siden parallell sortering er mulig i tid på prosessorer, kan kjøretiden til Kruskals algoritme reduseres til O ( E α ( V )), der α igjen er den omvendte av den enkeltverdige Ackermann-funksjonen . ${\ displaystyle O (n)}$${\ displaystyle O (\ log n)}$

En variant av Kruskals algoritme, kalt Filter-Kruskal, er beskrevet av Osipov et al. og er bedre egnet for parallellisering. Den grunnleggende ideen bak Filter-Kruskal er å dele kantene på en lignende måte som å kviksortere og filtrere ut kanter som forbinder hjørner av samme tre for å redusere kostnadene ved sortering. Følgende pseudokode demonstrerer dette.

function filter_kruskal(G) is
    if |G.E| < kruskal_threshold:
        return kruskal(G)
    pivot = choose_random(G.E)
    ${\displaystyle E_{\leq }}$, ${\displaystyle E_{>}}$ = partition(G.E, pivot)
    A = filter_kruskal(${\displaystyle E_{\leq }}$)
    ${\displaystyle E_{>}}$ = filter(${\displaystyle E_{>}}$)
    A = A ∪ filter_kruskal(${\displaystyle E_{>}}$)
    return A

function partition(E, pivot) is
    ${\displaystyle E_{\leq }}$ = ∅, ${\displaystyle E_{>}}$ = ∅
    foreach (u, v) in E do
        if weight(u, v) <= pivot then
            ${\displaystyle E_{\leq }}$ = ${\displaystyle E_{\leq }}$ ∪ {(u, v)}
        else
            ${\displaystyle E_{>}}$ = ${\displaystyle E_{>}}$ ∪ {(u, v)}
    return ${\displaystyle E_{\leq }}$, ${\displaystyle E_{>}}$

function filter(E) is
    ${\displaystyle E_{\text{filtered}}}$ = ∅
    foreach (u, v) in E do
        if find_set(u) ≠ find_set(v) then
            ${\displaystyle E_{\text{filtered}}}$ = ${\displaystyle E_{\text{filtered}}}$ ∪ {(u, v)}
    return ${\displaystyle E_{\text{filtered}}}$

Filter-Kruskal egner seg bedre for parallellisering, ettersom sortering, filtrering og partisjonering enkelt kan utføres parallelt ved å fordele kantene mellom prosessorene.

Til slutt er andre varianter av en parallell implementering av Kruskals algoritme blitt utforsket. Eksempler inkluderer et skjema som bruker hjelpetråder for å fjerne kanter som definitivt ikke er en del av MST i bakgrunnen, og en variant som kjører den sekvensielle algoritmen på p- underbilder, og deretter fletter disse underbildene til bare en, den endelige MST, gjenstår.

Se også

• Prims algoritme
• Dijkstras algoritme
• Borůvkas algoritme
• Slette-algoritme
• Klynging med enkelt kobling
• Grådig geometrisk skiftenøkkel

Referanser

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest og Clifford Stein . Introduksjon til algoritmer , andre utgave. MIT Press og McGraw-Hill, 2001. ISBN   0-262-03293-7 . Avsnitt 23.2: Algoritmene til Kruskal og Prim, s. 567–574.
• Michael T. Goodrich og Roberto Tamassia . Datastrukturer og algoritmer i Java , fjerde utgave. John Wiley & Sons, Inc., 2006. ISBN   0-471-73884-0 . Avsnitt 13.7.1: Kruskals algoritme, s. 632 ..

Eksterne linker

• Data for artikkelens eksempel .
• Gephi-plugin for beregning av et minimum kildekode for spennende tre .
• Kruskals algoritme med eksempel og program i c ++
• Kruskals algoritmekode i C ++ som brukt på tilfeldige tall
• Kruskals algoritmekode i Python med forklaring