Kruskals Algorithmus zum Überspannen von Bäumen mit einer Java-Implementierung

1. Übersicht

In einem früheren Artikel haben wir den Prim-Algorithmus vorgestellt, um die minimalen Spannbäume zu ermitteln. In diesem Artikel verwenden wir einen anderen Ansatz, den Kruskal-Algorithmus, um die minimalen und maximalen Spanning Tree-Probleme zu lösen.

2. Spanning Tree

Ein Spanning Tree eines ungerichteten Graphen ist ein verbundener Untergraph, der alle Graphenknoten mit der minimal möglichen Anzahl von Kanten abdeckt. Im Allgemeinen kann ein Graph mehr als einen Spanning Tree haben. Die folgende Abbildung zeigt ein Diagramm mit einem Spanning Tree (die Kanten des Spanning Tree sind rot):

Wenn das Diagramm kantengewichtet ist, können wir das Gewicht eines Spannbaums als die Summe der Gewichte aller seiner Kanten definieren. Ein minimaler Spannbaum ist ein Spannbaum, dessen Gewicht das kleinste unter allen möglichen Spannbäumen ist. Die folgende Abbildung zeigt einen minimalen Spannbaum in einem kantengewichteten Diagramm:

In ähnlicher Weise hat ein maximaler Spannbaum das größte Gewicht unter allen Spannbäumen. Die folgende Abbildung zeigt einen maximalen Spannbaum in einem kantengewichteten Diagramm:

3. Kruskals Algorithmus

In einem gegebenen Diagramm können wir den Kruskal-Algorithmus verwenden, um den minimalen Spannbaum zu ermitteln. Wenn die Anzahl der Knoten in einem Diagramm V ist , sollte jeder seiner Spannbäume (V-1) Kanten haben und keine Zyklen enthalten. Wir können Kruskals Algorithmus im folgenden Pseudocode beschreiben:

Initialize an empty edge set T. Sort all graph edges by the ascending order of their weight values. foreach edge in the sorted edge list Check whether it will create a cycle with the edges inside T. If the edge doesn't introduce any cycles, add it into T. If T has (V-1) edges, exit the loop. return T

Lassen Sie uns Schritt für Schritt den Kruskal-Algorithmus für einen minimalen Spannbaum in unserem Beispieldiagramm ausführen:

Zunächst wählen wir die Kante (0, 2), weil sie das kleinste Gewicht hat. Dann können wir die Kanten (3, 4) und (0, 1) hinzufügen, da sie keine Zyklen erzeugen. Jetzt ist der nächste Kandidat Kante (1, 2) mit Gewicht 9. Wenn wir diese Kante jedoch einschließen, erzeugen wir einen Zyklus (0, 1, 2). Daher verwerfen wir diese Kante und wählen weiterhin die nächstkleinere aus. Zum Abschluss addiert der Algorithmus die Kante (2, 4) des Gewichts 10.

Um den maximalen Spannbaum zu berechnen, können wir die Sortierreihenfolge in absteigende Reihenfolge ändern. Die anderen Schritte bleiben gleich. Die folgende Abbildung zeigt die schrittweise Erstellung eines maximalen Spannbaums in unserem Beispieldiagramm.

4. Zykluserkennung mit einem disjunkten Satz

In Kruskals Algorithmus besteht der entscheidende Teil darin, zu überprüfen, ob eine Kante einen Zyklus erzeugt, wenn wir ihn dem vorhandenen Kantensatz hinzufügen. Es gibt verschiedene Algorithmen zur Erkennung des Graphzyklus, die wir verwenden können. Zum Beispiel können wir einen DFS-Algorithmus (Depth First Search) verwenden, um den Graphen zu durchlaufen und festzustellen, ob ein Zyklus vorliegt.

Wir müssen jedoch jedes Mal eine Zykluserkennung an vorhandenen Kanten durchführen, wenn wir eine neue Kante testen. Eine schnellere Lösung besteht darin, den Union-Find-Algorithmus mit der disjunkten Datenstruktur zu verwenden, da er auch einen inkrementellen Ansatz zum Hinzufügen von Kanten verwendet, um Zyklen zu erkennen. Wir können dies in unseren Spanning Tree-Bauprozess integrieren.

4.1. Disjunkte Set- und Spanning Tree-Konstruktion

Zunächst behandeln wir jeden Knoten des Diagramms als eine einzelne Menge, die nur einen Knoten enthält. Dann prüfen wir jedes Mal, wenn wir eine Kante einführen, ob sich die beiden Knoten in derselben Menge befinden. Wenn die Antwort Ja lautet, wird ein Zyklus erstellt. Andernfalls führen wir die beiden disjunkten Sätze zu einem Satz zusammen und schließen die Kante für den Spanning Tree ein.

Wir können die obigen Schritte wiederholen, bis wir den gesamten Spanning Tree erstellt haben.

Zum Beispiel haben wir in der obigen minimalen Spanning Tree-Konstruktion zuerst 5 Knotensätze: {0}, {1}, {2}, {3}, {4}. Wenn wir die erste Kante (0, 2) überprüfen, befinden sich ihre beiden Knoten in unterschiedlichen Knotensätzen. Daher können wir diese Kante einschließen und {0} und {2} zu einer Menge {0, 2} zusammenführen.

Wir können ähnliche Operationen für die Kanten (3, 4) und (0, 1) durchführen. Die Knotensätze werden dann zu {0, 1, 2} und {3, 4}. Wenn wir die nächste Kante (1, 2) überprüfen, können wir sehen, dass sich beide Knoten dieser Kante in derselben Menge befinden. Daher verwerfen wir diese Kante und überprüfen die nächste weiter. Schließlich erfüllt die Kante (2, 4) unsere Bedingung, und wir können sie für den minimalen Spannbaum einschließen.

4.2. Disjunkte Set-Implementierung

Wir können eine Baumstruktur verwenden, um eine disjunkte Menge darzustellen. Jeder Knoten verfügt über einen übergeordneten Zeiger, der auf seinen übergeordneten Knoten verweist. In jedem Satz gibt es einen eindeutigen Wurzelknoten, der diesen Satz darstellt. Der Stammknoten verfügt über einen selbstreferenzierten übergeordneten Zeiger.

Verwenden wir eine Java-Klasse, um die disjunkten Mengeninformationen zu definieren:

public class DisjointSetInfo { private Integer parentNode; DisjointSetInfo(Integer parent) { setParentNode(parent); } //standard setters and getters }

Beschriften wir jeden Diagrammknoten mit einer Ganzzahl, beginnend mit 0. Wir können eine Listendatenstruktur, Listknoten , verwenden, um die disjunkten Mengeninformationen eines Diagramms zu speichern. Am Anfang ist jeder Knoten das repräsentative Mitglied seiner eigenen Menge:

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

4.3. Operation suchen

Um die Menge zu finden, zu der ein Knoten gehört, können wir der übergeordneten Kette des Knotens nach oben folgen, bis wir den Wurzelknoten erreichen:

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

Es ist möglich, eine stark unausgeglichene Baumstruktur für eine disjunkte Menge zu haben. Wir können die Verbesserung der Fund unter Verwendung der Operation p ath Kompressionstechnik.

Da jeder Knoten, den wir auf dem Weg zum Stammknoten besuchen, Teil derselben Gruppe ist, können wir den Stammknoten direkt an seine übergeordnete Referenz anhängen . Wenn wir diesen Knoten das nächste Mal besuchen, benötigen wir einen Suchpfad, um den Stammknoten zu erhalten:

Integer pathCompressionFind(Integer node) { DisjointSetInfo setInfo = nodes.get(node); Integer parent = setInfo.getParentNode(); if (parent.equals(node)) { return node; } else { Integer parentNode = find(parent); setInfo.setParentNode(parentNode); return parentNode; } }

4.4. Union Operation

Wenn sich die beiden Knoten einer Kante in unterschiedlichen Mengen befinden, kombinieren wir diese beiden Mengen zu einer. Wir können diese Vereinigungsoperation erreichen, indem wir die Wurzel eines repräsentativen Knotens auf den anderen repräsentativen Knoten setzen:

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

Diese einfache Vereinigungsoperation könnte einen stark unausgeglichenen Baum erzeugen, da wir einen zufälligen Wurzelknoten für die zusammengeführte Menge ausgewählt haben. Wir können die Leistung mithilfe einer Vereinigung nach Rang verbessern .

Since it is tree depth that affects the running time of the find operation, we attach the set with the shorter tree to the set with the longer tree. This technique only increases the depth of the merged tree if the original two trees have the same depth.

To achieve this, we first add a rank property to the DisjointSetInfo class:

public class DisjointSetInfo { private Integer parentNode; private int rank; DisjointSetInfo(Integer parent) { setParentNode(parent); setRank(0); } //standard setters and getters }

In the beginning, a single node disjoint has a rank of 0. During the union of two sets, the root node with a higher rank becomes the root node of the merged set. We increase the new root node's rank by one only if the original two ranks are the same:

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. Cycle Detection

We can determine whether two nodes are in the same disjoint set by comparing the results of two find operations. If they have the same representive root node, then we've detected a cycle. Otherwise, we merge the two disjoint sets by using a union operation:

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

The cycle detection, with the union by rank technique alone, has a running time of O(logV). We can achieve better performance with both path compression and union by rank techniques. The running time is O(α(V)), where α(V) is the inverse Ackermann function of the total number of nodes. It is a small constant that is less than 5 in our real-world computations.

5. Java Implementation of Kruskal’s Algorithm

We can use the ValueGraph data structure in Google Guava to represent an edge-weighted graph.

To use ValueGraph, we first need to add the Guava dependency to our project's pom.xml file:

     com.google.guava     guava     28.1-jre 

We can wrap the above cycle detection methods into a CycleDetector class and use it in Kruskal's algorithm. Since the minimum and maximum spanning tree construction algorithms only have a slight difference, we can use one general function to achieve both constructions:

ValueGraph spanningTree(ValueGraph graph, boolean minSpanningTree) { Set edges = graph.edges(); List edgeList = new ArrayList(edges); if (minSpanningTree) { edgeList.sort(Comparator.comparing(e -> graph.edgeValue(e).get())); } else { edgeList.sort(Collections.reverseOrder(Comparator.comparing(e -> graph.edgeValue(e).get()))); } int totalNodes = graph.nodes().size(); CycleDetector cycleDetector = new CycleDetector(totalNodes); int edgeCount = 0; MutableValueGraph spanningTree = ValueGraphBuilder.undirected().build(); for (EndpointPair edge : edgeList) { if (cycleDetector.detectCycle(edge.nodeU(), edge.nodeV())) { continue; } spanningTree.putEdgeValue(edge.nodeU(), edge.nodeV(), graph.edgeValue(edge).get()); edgeCount++; if (edgeCount == totalNodes - 1) { break; } } return spanningTree; }

In Kruskal's algorithm, we first sort all graph edges by their weights. This operation takes O(ElogE) time, where E is the total number of edges.

Dann verwenden wir eine Schleife, um die sortierte Kantenliste durchzugehen. In jeder Iteration prüfen wir, ob ein Zyklus gebildet wird, indem wir die Kante zum aktuellen Spanning Tree-Kantensatz hinzufügen. Diese Schleife mit der Zykluserkennung benötigt höchstens O (ElogV) Zeit.

Daher beträgt die Gesamtlaufzeit O (ELogE + ELogV) . Da der Wert von E in der Skala von O (V2) liegt , ist die zeitliche Komplexität des Kruskal-Algorithmus O (ElogE) oder O (ElogV) .

6. Fazit

In diesem Artikel haben wir gelernt, wie man den Kruskal-Algorithmus verwendet, um einen minimalen oder maximalen Spannbaum eines Graphen zu finden. Wie immer ist der Quellcode für den Artikel auf GitHub verfügbar.