streamalism.org

1. Oversigt

I en tidligere artikel introducerede vi Prims algoritme for at finde de mindst mulige træer. I denne artikel bruger vi en anden tilgang, Kruskals algoritme, til at løse de minimale og maksimale spændende træproblemer.

2. Spændende træ

Et spændende træ i en ikke-rettet graf er en tilsluttet undergraf, der dækker alle grafknudepunkter med det mindst mulige antal kanter. Generelt kan en graf have mere end et spændende træ. Følgende figur viser en graf med et spændende træ (kanterne på det spændende træ er i rødt):

Hvis grafen er kantvægtet, kan vi definere vægten af ​​et spændende træ som summen af ​​vægten af ​​alle dets kanter. Et minimum spændende træ er et spændende træ, hvis vægt er den mindste blandt alle mulige spændende træer. Følgende figur viser et minimum spændende træ på en kantvægtet graf:

Tilsvarende et maksimalt spændende træ har den største vægt blandt alle spændende træer. Følgende figur viser et maksimalt spændende træ på en kantvægtet graf:

3. Kruskals algoritme

På baggrund af en graf kan vi bruge Kruskals algoritme til at finde dens mindst spændende træ. Hvis antallet af noder i en graf er V, så skal hvert af dets spændende træer have (V-1) kanter og ikke indeholde cyklusser. Vi kan beskrive Kruskals algoritme i følgende pseudokode:

Initialiser et tomt kantsæt T. Sorter alle grafkanter efter stigende rækkefølge af deres vægtværdier. foreach edge i den sorterede kantliste Kontroller, om det vil skabe en cyklus med kanterne inden i T. Hvis kanten ikke introducerer nogen cyklusser, skal du tilføje den til T. Hvis T har (V-1) kanter, skal du afslutte loop. returnere T

Lad os køre Kruskals algoritme for et minimum, der spænder over træet i vores eksemplar graf trin for trin:

For det første vælger vi kanten (0, 2), fordi den har den mindste vægt. Derefter kan vi tilføje kanter (3, 4) og (0, 1), da de ikke opretter nogen cyklusser. Nu er den næste kandidat kant (1, 2) med vægt 9. Men hvis vi inkluderer denne kant, producerer vi en cyklus (0, 1, 2). Derfor kasserer vi denne kant og fortsætter med at vælge den næste mindste. Endelig slutter algoritmen ved at tilføje kanten (2, 4) af vægt 10.

For at beregne det maksimale spændende træ kan vi ændre sorteringsrækkefølgen til faldende rækkefølge. De andre trin forbliver de samme. Den følgende figur viser den trinvise konstruktion af et maksimalt spændende træ på vores eksempeldiagram.

4. Cyklusregistrering med et adskilt sæt

I Kruskals algoritme er den afgørende del at kontrollere, om en kant vil skabe en cyklus, hvis vi føjer den til det eksisterende kantsæt. Der er flere algoritmer til detektering af grafcyklusser, vi kan bruge. For eksempel kan vi bruge en DFS-algoritme til dybde-første søgning til at krydse grafen og opdage, om der er en cyklus.

Vi skal dog foretage en cyklusdetektion på eksisterende kanter hver gang, når vi tester en ny kant. En hurtigere løsning er at bruge Union-Find-algoritmen med den usammenhængende datastruktur, fordi den ogsåbruger en trinvis kanttilsætningsmetode til at detektere cyklusser. Vi kan passe dette ind i vores spændende trækonstruktionsproces.

4.1. Adskilt sæt og spændende trækonstruktion

For det første behandler vi hver node i grafen som et individuelt sæt, der kun indeholder en node. Derefter kontrollerer vi, om de to noder er i samme sæt, hver gang vi introducerer en kant. Hvis svaret er ja, opretter det en cyklus. Ellers fletter vi de to usammenhængende sæt i et sæt og inkluderer kanten til det spændende træ.

Vi kan gentage ovenstående trin, indtil vi konstruerer hele det spændende træ.

For eksempel har vi i ovenstående minimum spændende trækonstruktion fem nodesæt: {0}, {1}, {2}, {3}, {4}. Når vi kontrollerer den første kant (0, 2), er dens to noder i forskellige nodesæt. Derfor kan vi inkludere denne kant og flette {0} og {2} i et sæt {0, 2}.

Vi kan udføre lignende operationer for kanterne (3, 4) og (0, 1). Nodesættene bliver derefter {0, 1, 2} og {3, 4}. Når vi kontrollerer den næste kant (1, 2), kan vi se, at begge noder i denne kant er i samme sæt. Derfor kasserer vi denne kant og fortsætter med at kontrollere den næste. Endelig opfylder kanten (2, 4) vores tilstand, og vi kan inkludere den til det mindst mulige træ.

4.2. Disjoint Set Implementation

Vi kan bruge en træstruktur til at repræsentere et uensartet sæt. Hver knude har en forælder pointer for at henvise til dets overordnede node. I hvert sæt er der en unik rodnode, der repræsenterer dette sæt. Rodknuden har en selvhenvisning forælder markør.

Lad os bruge en Java-klasse til at definere oplysningerne om usammenhængende sæt:

offentlig klasse DisjointSetInfo {privat Heltal parentNode; DisjointSetInfo (Heltalsforælder) {setParentNode (forælder); } // standard settere og getters}

Lad os mærke hver grafknude med et heltal, startende fra 0. Vi kan bruge en datadatastruktur, Liste noder, for at gemme de usammenhængende oplysninger om en graf. I starten er hver node det repræsentative medlem af sit eget sæt:

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

4.3. Find operation

For at finde det sæt, som en node tilhører, kan vi følge nodens moderkæde opad, indtil vi når rodnoden:

Heltalsfinding (Heltalsnode) {Heltalsforælder = nodes.get (node) .getParentNode (); if (parent.equals (node)) {return node; } andet {return find (forælder); }}

Det er muligt at have en meget ubalanceret træstruktur til et uensartet sæt. Vi kan forbedre finde betjening ved hjælp af sath kompression teknik.

Da hver node, vi besøger på vej til rodnoden, er en del af det samme sæt, kan vi vedhæfte rodnoden til dens forælder henvisning direkte. Næste gang når vi besøger denne node, har vi brug for en opslagssti for at få rodnoden:

Integer pathCompressionFind (Integer node) {DisjointSetInfo setInfo = nodes.get (node); Heltalsforælder = setInfo.getParentNode (); if (parent.equals (node)) {return node; } andet {Integer parentNode = find (forælder); setInfo.setParentNode (parentNode); returner parentNode; }}

4.4. Unionens operation

Hvis de to noder i en kant er i forskellige sæt, kombinerer vi disse to sæt til et. Vi kan opnå dette Union operation ved at indstille roden til en repræsentativ node til den anden repræsentative node:

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

Denne enkle foreningshandling kunne producere et meget ubalanceret træ, da vi valgte en tilfældig rodnode til det flettede sæt. Vi kan forbedre ydeevnen ved hjælp af en fagforening efter rang teknik.

Da det er trædybde, der påvirker kørselstiden for finde operation, vi fastgør sættet med det kortere træ til sættet med det længere træ. Denne teknik øger kun dybden af ​​det flettede træ, hvis de to originale træer har samme dybde.

For at opnå dette tilføjer vi først en rang ejendom til DisjointSetInfo klasse:

offentlig klasse DisjointSetInfo {privat Heltal parentNode; privat int rang; DisjointSetInfo (Heltalsforælder) {setParentNode (forælder); setRank (0); } // standard settere og getters}

I begyndelsen har en enkelt knudesammenkobling en rang på 0. Under foreningen af ​​to sæt bliver rodknudepunktet med en højere rang rodknudepunktet for det flettede sæt. Vi øger den nye rodknudes rang kun med en, hvis de oprindelige to rækker er ens:

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

4.5. Cyklusregistrering

Vi kan afgøre, om to noder er i samme usammenhængende sæt ved at sammenligne resultaterne af to finde operationer. Hvis de har den samme repræsentative rodnode, har vi registreret en cyklus. Ellers fletter vi de to usammenhængende sæt ved hjælp af a Union operation:

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

Cyklusdetektering med fagforening efter rang teknik alene, har en løbetid på O (logV). Vi kan opnå bedre præstationer med begge stykompression og fagforening efter rang teknikker. Løbetiden er O (α (V)), hvor α (V) er den inverse Ackermann-funktion af det samlede antal noder. Det er en lille konstant, der er mindre end 5 i vores virkelige beregninger.

5. Java-implementering af Kruskals algoritme

Vi kan bruge ValueGraph datastruktur i Google Guava til at repræsentere en kantvægtet graf.

At bruge ValueGraph, skal vi først tilføje Guava-afhængighed til vores projekts pom.xml fil:

     com.google.guava guava 28.1-jre 

Vi kan pakke ovennævnte cyklusdetektionsmetoder ind i en CycleDetector klasse og bruge den i Kruskals algoritme. Da minimums- og maksimumomspændende trækonstruktionsalgoritmer kun har en lille forskel, kan vi bruge en generel funktion til at opnå begge konstruktioner:

ValueGraph spanningTree (ValueGraph-graf, boolsk minSpanningTree) {Sæt kanter = graph.edges (); Liste edgeList = ny ArrayList (kanter); hvis (minSpanningTree) {edgeList.sort (Comparator.comparing (e -> graph.edgeValue (e) .get ())); ellers {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 ())) {fortsæt; } 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 efter deres vægt. Denne operation tager O (ElogE) tid, hvor E er det samlede antal kanter.

Derefter bruger vi en løkke til at gå gennem den sorterede kantliste. I hver iteration kontrollerer vi, om en cyklus vil blive dannet ved at tilføje kanten i det nuværende spændende trækantsæt. Denne sløjfe med cyklusregistreringen tager højst O (ElogV) tid.

Derfor er den samlede køretid O (ELogE + ELogV). Da værdien af E er i skalaen af O (V2)er tidskompleksiteten af ​​Kruskals algoritme O (ElogE) eller O (ElogV).

6. Konklusion

I denne artikel lærte vi, hvordan man bruger Kruskals algoritme til at finde et minimum eller maksimalt spændende træ i en graf. Som altid er kildekoden til artiklen tilgængelig på GitHub.