streamalism.org

1. Overzicht

In een vorig artikel hebben we het algoritme van Prim geïntroduceerd om de minimale spanning trees te vinden. In dit artikel gebruiken we een andere benadering, het algoritme van Kruskal, om de minimale en maximale spanning tree-problemen op te lossen.

2. Boom overspannen

Een opspannende boom van een ongerichte graaf is een verbonden subgraaf die alle graafknooppunten beslaat met een zo klein mogelijk aantal randen. In het algemeen kan een graaf meer dan één opspannende boom hebben. De volgende afbeelding toont een grafiek met een spanning tree (randen van de spanning tree zijn in rood):

Als de grafiek randgewogen is, kunnen we het gewicht van een opspannende boom definiëren als de som van de gewichten van al zijn randen. Een minimaal opspannende boom is een opspannende boom waarvan het gewicht het kleinst is van alle mogelijke opspannende bomen. De volgende afbeelding toont een minimale spanning tree op een randgewogen grafiek:

Evenzo een maximale opspannende boom heeft het grootste gewicht van alle opspannende bomen. De volgende afbeelding toont een maximale spanning tree op een randgewogen grafiek:

3. Het algoritme van Kruskal

Gegeven een grafiek, kunnen we het algoritme van Kruskal gebruiken om de minimale spanning tree te vinden. Als het aantal knooppunten in een grafiek is V., dan moet elk van de opspannende bomen (V-1) randen hebben en geen cycli bevatten. We kunnen het algoritme van Kruskal beschrijven in de volgende pseudo-code:

Initialiseer een set met lege randen T. Sorteer alle grafiekranden in oplopende volgorde van hun gewichtswaarden. voor elke rand in de gesorteerde randlijst Controleer of er een cyclus ontstaat met de randen binnen T. Als de rand geen cycli introduceert, voeg deze dan toe aan T. Als T (V-1) randen heeft, verlaat de lus. terug T

Laten we het algoritme van Kruskal stap voor stap uitvoeren voor een minimale spanning tree in onze voorbeeldgrafiek:

Ten eerste kiezen we de rand (0, 2) omdat deze het kleinste gewicht heeft. Vervolgens kunnen we randen (3, 4) en (0, 1) toevoegen omdat ze geen cycli creëren. Nu is de volgende kandidaat rand (1, 2) met gewicht 9. Als we deze rand echter opnemen, produceren we een cyclus (0, 1, 2). Daarom gooien we deze rand weg en blijven we de volgende kleinste kiezen. Ten slotte eindigt het algoritme door de rand (2, 4) van gewicht 10 toe te voegen.

Om de maximale spanning tree te berekenen, kunnen we de sorteervolgorde wijzigen in aflopende volgorde. De andere stappen blijven hetzelfde. De volgende afbeelding toont de stapsgewijze constructie van een maximale spanning tree in onze voorbeeldgrafiek.

4. Cyclusdetectie met een onsamenhangende set

In het algoritme van Kruskal is het cruciale onderdeel om te controleren of een rand een cyclus zal creëren als we deze toevoegen aan de bestaande randset. Er zijn verschillende algoritmen voor het detecteren van grafische cycli die we kunnen gebruiken. We kunnen bijvoorbeeld een DFS-algoritme (depth-first search) gebruiken om door de grafiek te lopen en te detecteren of er een cyclus is.

We moeten echter elke keer dat we een nieuwe snede testen een cyclusdetectie uitvoeren op bestaande snijkanten. Een snellere oplossing is om het Union-Find-algoritme te gebruiken met de onsamenhangende datastructuur, omdat het ookgebruikt een incrementele randtoevoegingsbenadering om cycli te detecteren. Dit kunnen we inpassen in ons spannende boomconstructieproces.

4.1. Disjuncte set en overspannen boomconstructie

Ten eerste behandelen we elk knooppunt van de grafiek als een individuele set die slechts één knooppunt bevat. Elke keer dat we een rand introduceren, controleren we vervolgens of de twee knooppunten zich in dezelfde set bevinden. Als het antwoord ja is, ontstaat er een cyclus. Anders voegen we de twee disjuncte sets samen tot één set en nemen we de rand voor de spanning tree op.

We kunnen de bovenstaande stappen herhalen totdat we de hele opspannende boom construeren.

In de bovenstaande minimale spanning tree-constructie hebben we bijvoorbeeld eerst 5 knooppuntsets: {0}, {1}, {2}, {3}, {4}. Wanneer we de eerste rand (0, 2) controleren, bevinden de twee knooppunten zich in verschillende knooppuntsets. Daarom kunnen we deze rand opnemen en {0} en {2} samenvoegen tot één set {0, 2}.

We kunnen soortgelijke bewerkingen uitvoeren voor de randen (3, 4) en (0, 1). De knooppuntsets worden dan {0, 1, 2} en {3, 4}. Als we de volgende rand (1, 2) controleren, kunnen we zien dat beide knooppunten van deze rand in dezelfde set zitten. Daarom gooien we deze rand weg en gaan we door met het controleren van de volgende. Ten slotte voldoet de rand (2, 4) aan onze voorwaarde en kunnen we deze opnemen voor de minimale opspannende boom.

4.2. Onsamenhangende setimplementatie

We kunnen een boomstructuur gebruiken om een ​​onsamenhangende verzameling weer te geven. Elk knooppunt heeft een ouder pointer om naar het bovenliggende knooppunt te verwijzen. In elke set is er een uniek hoofdknooppunt dat deze set vertegenwoordigt. Het hoofdknooppunt heeft een zelfverwijzend ouder wijzer.

Laten we een Java-klasse gebruiken om de disjuncte set-informatie te definiëren:

openbare klasse DisjointSetInfo {privé Geheel getal parentNode; DisjointSetInfo (bovenliggend geheel getal) {setParentNode (bovenliggend); } // standaard setters en getters}

Laten we elk grafiekknooppunt labelen met een geheel getal, beginnend bij 0. We kunnen een lijstgegevensstructuur gebruiken, Lijst met knooppunten, om de onsamenhangende setinformatie van een grafiek op te slaan. In het begin is elk knooppunt het representatieve lid van zijn eigen set:

void initDisjointSets (int totalNodes) {nodes = nieuwe ArrayList (totalNodes); voor (int i = 0; i <totalNodes; i ++) {nodes.add (nieuwe DisjointSetInfo (i)); }} 

4.3. Zoek operatie

Om de set te vinden waartoe een knooppunt behoort, kunnen we de bovenliggende keten van het knooppunt naar boven volgen totdat we het hoofdknooppunt bereiken:

Integer find (Integer node) {Integer parent = nodes.get (node) .getParentNode (); if (parent.equals (node)) {retourknooppunt; } else {return find (ouder); }}

Het is mogelijk om een ​​zeer ongebalanceerde boomstructuur te hebben voor een disjuncte set. We kunnen het vind bediening met behulp van de path compressie techniek.

Omdat elk knooppunt dat we bezoeken op weg naar het hoofdknooppunt deel uitmaakt van dezelfde set, kunnen we het hoofdknooppunt aan zijn ouder verwijzing rechtstreeks. De volgende keer dat we dit knooppunt bezoeken, hebben we één opzoekpad nodig om het hoofdknooppunt te krijgen:

Geheel getal pathCompressionFind (Integer node) {DisjointSetInfo setInfo = nodes.get (node); Geheel getal ouder = setInfo.getParentNode (); if (parent.equals (node)) {retourknooppunt; } else {Geheel getal parentNode = find (bovenliggend); setInfo.setParentNode (parentNode); retourneer parentNode; }}

4.4. Operatie van de Unie

Als de twee knooppunten van een rand zich in verschillende sets bevinden, combineren we deze twee sets tot één. We kunnen dit bereiken unie bewerking door de root van het ene representatieve knooppunt in te stellen op het andere representatieve knooppunt:

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

Deze eenvoudige samenvoegingsoperatie zou een zeer ongebalanceerde boom kunnen produceren als we een willekeurig rootknooppunt voor de samengevoegde set kozen. We kunnen de prestaties verbeteren met een vereniging op rang techniek.

Omdat het de boomdiepte is die de looptijd van de vind operatie, we bevestigen de set met de kortere boom aan de set met de langere boom. Deze techniek vergroot de diepte van de samengevoegde boom alleen als de oorspronkelijke twee bomen dezelfde diepte hebben.

Om dit te bereiken voegen we eerst een rang eigendom aan de DisjointSetInfo klasse:

openbare klasse DisjointSetInfo {privé Geheel getal parentNode; private int rang; DisjointSetInfo (bovenliggend geheel getal) {setParentNode (bovenliggend); setRank (0); } // standaard setters en getters}

In het begin heeft een enkel disjunct-knooppunt een rang van 0. Tijdens de vereniging van twee sets wordt het hoofdknooppunt met een hogere rang het hoofdknooppunt van de samengevoegde set. We verhogen de rang van de nieuwe root-node alleen met één als de oorspronkelijke twee rangen hetzelfde zijn:

void unionByRank (int rootU, int rootV) {DisjointSetInfo setInfoU = nodes.get (rootU); DisjointSetInfo setInfoV = nodes.get (rootV); int rankU = setInfoU.getRank (); int rankV = setInfoV.getRank (); if (rankU <rankV) {setInfoU.setParentNode (rootV); } else {setInfoV.setParentNode (rootU); if (rankU == rankV) {setInfoU.setRank (rankU + 1); }}}

4.5. Cyclus detectie

We kunnen bepalen of twee knooppunten zich in dezelfde disjuncte set bevinden door de resultaten van twee te vergelijken vind operaties. Als ze hetzelfde representatieve hoofdknooppunt hebben, hebben we een cyclus gedetecteerd. Anders voegen we de twee disjuncte sets samen met een unie operatie:

boolean detectCycle (Geheel getal u, Geheel getal v) {Geheel getal rootU = pathCompressionFind (u); Geheel getal rootV = pathCompressionFind (v); if (rootU.equals (rootV)) {return true; } unionByRank (rootU, rootV); teruggeven false; } 

De cyclusdetectie, met de vereniging op rang techniek alleen, heeft een looptijd van O (logV). Met beide kunnen we betere prestaties behalen pad compressie en vereniging op rang technieken. De looptijd is O (α (V)), waar α (V) is de inverse Ackermann-functie van het totale aantal knooppunten. Het is een kleine constante die kleiner is dan 5 in onze berekeningen in de echte wereld.

5. Java-implementatie van het algoritme van Kruskal

We kunnen de Waardegrafiek datastructuur in Google Guava om een ​​randgewogen grafiek weer te geven.

Gebruiken Waardegrafiek, moeten we eerst de Guava-afhankelijkheid toevoegen aan die van ons project pom.xml het dossier:

     com.google.guava guave 28.1-jre 

We kunnen de bovenstaande cyclusdetectiemethoden verpakken in een CycleDetector class en gebruik het in het algoritme van Kruskal. Aangezien de minimale en maximale spanning tree constructie-algoritmen slechts een klein verschil hebben, kunnen we één algemene functie gebruiken om beide constructies te bereiken:

ValueGraph spanningTree (ValueGraph-grafiek, boolean minSpanningTree) {Set randen = graph.edges (); Lijst edgeList = nieuwe ArrayList (randen); if (minSpanningTree) {edgeList.sort (Comparator.comparing (e -> graph.edgeValue (e) .get ())); } anders {edgeList.sort (Collections.reverseOrder (Comparator.comparing (e -> graph.edgeValue (e) .get ()))); } int totalNodes = graph.nodes (). size (); CycleDetector cycleDetector = nieuwe CycleDetector (totalNodes); int edgeCount = 0; MutableValueGraph spanningTree = ValueGraphBuilder.undirected (). Build (); voor (EndpointPair edge: edgeList) {if (cycleDetector.detectCycle (edge.nodeU (), edge.nodeV ())) {ga verder; } spanningTree.putEdgeValue (edge.nodeU (), edge.nodeV (), graph.edgeValue (edge) .get ()); edgeCount ++; if (edgeCount == totalNodes - 1) {break; }} terugkeer spanningTree; }

In het algoritme van Kruskal sorteren we eerst alle grafiekranden op gewicht. Deze operatie duurt O (ElogE) tijd, waar E. is het totale aantal randen.

Vervolgens gebruiken we een lus om door de gesorteerde randlijst te gaan. Bij elke iteratie controleren we of er een cyclus wordt gevormd door de rand toe te voegen aan de huidige opspannende boomrandset. Deze lus met de cyclusdetectie duurt maximaal O (ElogV) tijd.

Daarom is de totale looptijd O (ELogE + ELogV). Sinds de waarde van E. is in de schaal van O (V2), de tijdcomplexiteit van het algoritme van Kruskal is O (ElogE) of O (ElogV).

6. Conclusie

In dit artikel hebben we geleerd hoe we het algoritme van Kruskal kunnen gebruiken om een ​​minimale of maximale spanning tree van een grafiek te vinden. Zoals altijd is de broncode voor het artikel beschikbaar op GitHub.