streamalism.org

1. Oversikt

I en tidligere artikkel introduserte vi Prims algoritme for å finne minimum spennende trær. I denne artikkelen vil vi bruke en annen tilnærming, Kruskals algoritme, for å løse de minste og maksimale spenningsproblemene.

2. Spennende tre

Et spennende tre i en ikke-rettet graf er en sammenkoblet undergraf som dekker alle grafnodene med minst mulig antall kanter. Generelt kan en graf ha mer enn ett spennende tre. Følgende figur viser en graf med et spennende tre (kantene på det spennende treet er i rødt):

Hvis grafen er kantvektet, kan vi definere vekten til et spennende tre som summen av vekten av alle kantene. Et minimum spennende tre er et spennende tre hvis vekt er den minste blant alle mulige spennende trær. Følgende figur viser et minimum spennende tre på en kantvektet graf:

På samme måte, et maksimalt spennende tre har den største vekten blant alle spennende trær. Følgende figur viser et maksimalt spennende tre på en kantvektet graf:

3. Kruskals algoritme

Gitt en graf, kan vi bruke Kruskals algoritme til å finne det minste spennende treet. Hvis antall noder i en graf er V, så skal hvert av sine spennende trær ha (V-1) kanter og ikke inneholde sykluser. Vi kan beskrive Kruskals algoritme i følgende pseudokode:

Initialiser et tomt kantsett T. Sorter alle grafkanter etter stigende rekkefølge på vektverdiene. foreach edge i den sorterte kantlisten Sjekk om det vil skape en syklus med kantene inni T. Hvis kanten ikke introduserer noen sykluser, kan du legge den til i T. Hvis T har (V-1) kanter, gå ut av loop. returner T

La oss kjøre Kruskals algoritme for et minimumspennende tre på vår eksempeldiagram trinn for trinn:

For det første velger vi kanten (0, 2) fordi den har den minste vekten. Deretter kan vi legge til kanter (3, 4) og (0, 1) ettersom de ikke lager noen sykluser. Nå er neste kandidat kant (1, 2) med vekt 9. Men hvis vi inkluderer denne kanten, vil vi produsere en syklus (0, 1, 2). Derfor forkaster vi denne kanten og fortsetter å velge den neste minste. Til slutt avsluttes algoritmen ved å legge til kanten (2, 4) av vekt 10.

For å beregne det maksimale spennende treet, kan vi endre sorteringsrekkefølgen til synkende rekkefølge. De andre trinnene forblir de samme. Figuren nedenfor viser trinn-for-trinn-konstruksjonen av et maksimalt spennende tre på vår eksempeldiagram.

4. Syklusdeteksjon med et usammenhengende sett

I Kruskals algoritme er den avgjørende delen å sjekke om en kant vil skape en syklus hvis vi legger den til det eksisterende kantsettet. Det er flere algoritmer for deteksjon av grafsykluser vi kan bruke. For eksempel kan vi bruke en DFS-algoritme for dybdeforsøk for å krysse grafen og oppdage om det er en syklus.

Vi må imidlertid gjøre en syklusdeteksjon på eksisterende kanter hver gang vi tester en ny kant. En raskere løsning er å bruke Union-Find-algoritmen med den usammenhengende datastrukturen fordi den ogsåbruker en inkrementell kanttilsetningsmetode for å oppdage sykluser. Vi kan passe dette inn i vår omfattende trekonstruksjonsprosess.

4.1. Separat sett og spennende trekonstruksjon

For det første behandler vi hver node i grafen som et individuelt sett som bare inneholder en node. Hver gang vi introduserer en kant, sjekker vi om de to nodene er i samme sett. Hvis svaret er ja, vil det skape en syklus. Ellers slår vi sammen de to usammenhengende settene i ett sett og inkluderer kanten for det spennende treet.

Vi kan gjenta trinnene ovenfor til vi konstruerer hele det spennende treet.

For eksempel, i det ovennevnte minimumet av trekonstruksjon, har vi først fem nodesett: {0}, {1}, {2}, {3}, {4}. Når vi sjekker den første kanten (0, 2), er de to nodene i forskjellige nodesett. Derfor kan vi inkludere denne kanten og slå sammen {0} og {2} i ett sett {0, 2}.

Vi kan gjøre lignende operasjoner for kantene (3, 4) og (0, 1). Nodesettene blir da {0, 1, 2} og {3, 4}. Når vi sjekker neste kant (1, 2), kan vi se at begge nodene til denne kanten er i samme sett. Derfor forkaster vi denne kanten og fortsetter å sjekke den neste. Til slutt tilfredsstiller kanten (2, 4) vår tilstand, og vi kan inkludere den for det minste spennende treet.

4.2. Disjoint Set Implementation

Vi kan bruke en trestruktur for å representere et uensartet sett. Hver node har en foreldre pekeren for å referere til den overordnede noden. I hvert sett er det en unik rotnode som representerer dette settet. Rotnoden har en egenhenvisning foreldre pekeren.

La oss bruke en Java-klasse for å definere informasjonen om usammenhengende sett:

offentlig klasse DisjointSetInfo {private Integer parentNode; DisjointSetInfo (Integer parent) {setParentNode (parent); } // standard settere og getters}

La oss merke hver grafnode med et helt tall, fra 0. Vi kan bruke en datadatastruktur, Liste noder, for å lagre den usammenhengende informasjonen til en graf. I begynnelsen er hver node representant for sitt eget sett:

ugyldig initDisjointSets (int totalNodes) {nodes = new ArrayList (totalNodes); for (int i = 0; i <totalNodes; i ++) {nodes.add (new DisjointSetInfo (i)); }} 

4.3. Finn operasjon

For å finne settet som en node tilhører, kan vi følge nodens foreldrekjede oppover til vi når rotnoden:

Heltallfunn (Heltallnode) {Heltallforelder = nodes.get (node) .getParentNode (); if (parent.equals (node)) {retur node; } annet {return find (foreldre); }}

Det er mulig å ha en svært ubalansert trestruktur for et usammenhengende sett. Vi kan forbedre finne ved å bruke sath komprimering teknikk.

Siden hver node vi besøker på vei til rotnoden er en del av samme sett, kan vi feste rotnoden til dens foreldre referanse direkte. Neste gang vi besøker denne noden, trenger vi en oppslagsbane for å få rotnoden:

Integer pathCompressionFind (Integer node) {DisjointSetInfo setInfo = nodes.get (node); Heltalsforelder = setInfo.getParentNode (); if (parent.equals (node)) {retur node; } annet {Integer parentNode = find (parent); setInfo.setParentNode (foreldrenode); returner parentNode; }}

4.4. Union Operation

Hvis de to nodene til en kant er i forskjellige sett, kombinerer vi disse to settene i ett. Vi kan oppnå dette fagforening operasjon ved å sette roten til en representativ node til den andre representative node:

ugyldig union (Integer rootU, Integer rootV) {DisjointSetInfo setInfoU = nodes.get (rootU); setInfoU.setParentNode (rootV); }

Denne enkle foreningsoperasjonen kan produsere et svært ubalansert tre da vi valgte en tilfeldig rotnode for det sammenslåtte settet. Vi kan forbedre ytelsen ved hjelp av en fagforening etter rang teknikk.

Siden det er tredybde som påvirker kjøretiden til finne operasjon, vi fester settet med det kortere treet til settet med det lengre treet. Denne teknikken øker bare dybden på det sammenslåtte treet hvis de opprinnelige to trærne har samme dybde.

For å oppnå dette legger vi først til en rang eiendom til DisjointSetInfo klasse:

offentlig klasse DisjointSetInfo {private Integer parentNode; privat int rang; DisjointSetInfo (Integer parent) {setParentNode (parent); setRank (0); } // standard settere og getters}

I begynnelsen har en enkelt node-usammenheng en rangering på 0. Under foreningen av to sett blir rotnoden med høyere rang rotnoden til det sammenslåtte settet. Vi øker den nye rotnodens rangering med en bare hvis de to opprinnelige rekkene er de samme:

ugyldig unionByRank (int rootU, int rootV) {DisjointSetInfo setInfoU = nodes.get (rootU); DisjointSetInfo setInfoV = nodes.get (rootV); int rangU = setInfoU.getRank (); int rangV = setInfoV.getRank (); hvis (rangU <rangV) {setInfoU.setParentNode (rootV); } annet {setInfoV.setParentNode (rootU); hvis (rangU == rangV) {setInfoU.setRank (rangU + 1); }}}

4.5. Syklusregistrering

Vi kan bestemme om to noder er i samme usammenhengende sett ved å sammenligne resultatene av to finne operasjoner. Hvis de har samme representative rotnode, har vi oppdaget en syklus. Ellers slår vi sammen de to usammenhengende settene ved å bruke a fagforening operasjon:

boolsk detectCycle (Integer u, Integer v) {Integer rootU = pathCompressionFind (u); Heltall rootV = pathCompressionFind (v); hvis (rootU.equals (rootV)) {return true; } unionByRank (rootU, rootV); returner falsk; } 

Syklusdeteksjonen, med fagforening etter rang teknikk alene, har en kjøretid på O (logV). Vi kan oppnå bedre ytelse med begge banekomprimering og fagforening etter rang teknikker. Kjøretiden er O (α (V)), hvor α (V) er den omvendte Ackermann-funksjonen til det totale antallet noder. Det er en liten konstant som er mindre enn 5 i våre virkelige beregninger.

5. Java Implementation of Kruskal’s Algorithm

Vi kan bruke ValueGraph datastruktur i Google Guava for å representere en kantvektet graf.

Å bruke ValueGraph, må vi først legge til Guava-avhengigheten til prosjektet vårt pom.xml fil:

     com.google.guava guava 28.1-jre 

Vi kan pakke de ovennevnte syklusdeteksjonsmetodene inn i en CycleDetector klasse og bruke den i Kruskals algoritme. Siden minimums- og maksimalomspennende trekonstruksjonsalgoritmer bare har en liten forskjell, kan vi bruke en generell funksjon for å oppnå begge konstruksjonene:

ValueGraph spanningTree (ValueGraph-graf, boolsk minSpanningTree) {Sett kanter = graph.edges (); Liste edgeList = ny ArrayList (kanter); hvis (minSpanningTree) {edgeList.sort (Comparator.comparing (e -> graph.edgeValue (e) .get ())); } annet {edgeList.sort (Collections.reverseOrder (Comparator.comparing (e -> graph.edgeValue (e) .get ()))); } int totalNodes = graph.nodes (). størrelse (); CycleDetector cycleDetector = ny CycleDetector (totalNodes); int edgeCount = 0; MutableValueGraph spanningTree = ValueGraphBuilder.undirected (). Build (); for (EndpointPair edge: edgeList) {if (cycleDetector.detectCycle (edge.nodeU (), edge.nodeV ())) {fortsett; } spanningTree.putEdgeValue (edge.nodeU (), edge.nodeV (), graph.edgeValue (edge) .get ()); edgeCount ++; if (edgeCount == totalNodes - 1) {pause; }} returner spanningTree; }

I Kruskals algoritme sorterer vi først alle grafkanter etter vektene. Denne operasjonen tar O (ElogE) tid, hvor E er det totale antallet kanter.

Deretter bruker vi en løkke for å gå gjennom den sorterte kantlisten. I hver iterasjon sjekker vi om en syklus vil bli dannet ved å legge kanten inn i det nåværende spennende trekant settet. Denne sløyfen med syklusdeteksjonen tar maksimalt O (ElogV) tid.

Derfor er den totale kjøretiden O (ELogE + ELogV). Siden verdien av E er i skalaen til O (V2), tidskompleksiteten til Kruskals algoritme er O (ElogE) eller O (ElogV).

6. Konklusjon

I denne artikkelen lærte vi hvordan vi bruker Kruskals algoritme for å finne et minimum eller maksimalt spennende tre i en graf. Som alltid er kildekoden for artikkelen tilgjengelig på GitHub.