Boruvkas Algorithmus für Minimum Spanning Trees in Java

1. Übersicht

In diesem Tutorial werfen wir einen Blick auf die Java-Implementierung des Boruvka-Algorithmus zum Ermitteln eines Minimum Spanning Tree (MST) eines kantengewichteten Diagramms .

Es ist älter als die Algorithmen von Prim und Kruskal, kann aber dennoch als Kreuzung zwischen beiden betrachtet werden.

2. Boruvkas Algorithmus

Wir werden direkt in den vorliegenden Algorithmus springen. Schauen wir uns ein bisschen Geschichte und dann den Algorithmus selbst an.

2.1. Geschichte

Ein Weg, einen MST eines bestimmten Graphen zu finden, wurde erstmals 1926 von Otakar Boruvka formuliert. Dies war lange bevor es überhaupt Computer gab, und wurde tatsächlich modelliert, um ein effizientes Stromverteilungssystem zu entwerfen.

Georges Sollin entdeckte es 1965 wieder und verwendete es für paralleles Rechnen.

2.2. Der Algorithmus

Die zentrale Idee des Algorithmus besteht darin, mit einer Reihe von Bäumen zu beginnen, wobei jeder Scheitelpunkt einen isolierten Baum darstellt. Dann müssen wir immer wieder Kanten hinzufügen, um die Anzahl der isolierten Bäume zu verringern, bis wir einen einzigen verbundenen Baum haben.

Lassen Sie uns dies in Schritten mit einem Beispieldiagramm sehen:

  • Schritt 0: Erstellen Sie ein Diagramm
  • Schritt 1: Beginnen Sie mit einer Reihe nicht verbundener Bäume (Anzahl der Bäume = Anzahl der Eckpunkte)
  • Schritt 2: Während es nicht verbundene Bäume gibt, für jeden nicht verbundenen Baum:
    • finden Sie seine Kante mit geringerem Gewicht
    • Fügen Sie diese Kante hinzu, um einen weiteren Baum zu verbinden

3. Java-Implementierung

Nun wollen wir sehen, wie wir dies in Java implementieren können.

3.1. Die UnionFind- Datenstruktur

Mit zu beginnen, brauchen wir eine Datenstruktur , die Eltern und Reihen unserer Eckpunkten zu speichern .

Definieren wir zu diesem Zweck eine Klasse UnionFind mit zwei Methoden: union und find :

public class UnionFind { private int[] parents; private int[] ranks; public UnionFind(int n) { parents = new int[n]; ranks = new int[n]; for (int i = 0; i < n; i++) { parents[i] = i; ranks[i] = 0; } } public int find(int u) { while (u != parents[u]) { u = parents[u]; } return u; } public void union(int u, int v) { int uParent = find(u); int vParent = find(v); if (uParent == vParent) { return; } if (ranks[uParent]  ranks[vParent]) { parents[vParent] = uParent; } else { parents[vParent] = uParent; ranks[uParent]++; } } } 

Wir können uns diese Klasse als eine Hilfsstruktur vorstellen, um die Beziehungen zwischen unseren Eckpunkten aufrechtzuerhalten und unseren MST schrittweise aufzubauen.

Um herauszufinden, ob zwei Eckpunkte u und v zum selben Baum gehören , prüfen wir, ob find (u) dasselbe übergeordnete Element wie find (v) zurückgibt . Die Vereinigungsmethode wird verwendet, um Bäume zu kombinieren. Wir werden diese Verwendung in Kürze sehen.

3.2. Geben Sie ein Diagramm vom Benutzer ein

Jetzt brauchen wir eine Möglichkeit, die Eckpunkte und Kanten eines Graphen vom Benutzer abzurufen und sie Objekten zuzuordnen, die wir zur Laufzeit in unserem Algorithmus verwenden können.

Da wir JUnit zum Testen unseres Algorithmus verwenden, wird dieser Teil in einer @ Before- Methode ausgeführt:

@Before public void setup() { graph = ValueGraphBuilder.undirected().build(); graph.putEdgeValue(0, 1, 8); graph.putEdgeValue(0, 2, 5); graph.putEdgeValue(1, 2, 9); graph.putEdgeValue(1, 3, 11); graph.putEdgeValue(2, 3, 15); graph.putEdgeValue(2, 4, 10); graph.putEdgeValue(3, 4, 7); } 

Hier haben wir Guavas MutableValueGraph verwendet , um unser Diagramm zu speichern. Dann haben wir ValueGraphBuilder verwendet , um ein ungerichtetes gewichtetes Diagramm zu erstellen .

Die Methode putEdgeValue verwendet drei Argumente, zwei Ganzzahlen für die Eckpunkte und die dritte Ganzzahl für ihre Gewichtung, wie in der generischen Typdeklaration von MutableValueGraph angegeben .

Wie wir sehen können, ist dies die gleiche Eingabe wie in unserem Diagramm von früher.

3.3. Leiten Sie den minimalen Spanning Tree ab

Schließlich kommen wir zum Kern der Sache, der Implementierung des Algorithmus.

Wir machen das in einer Klasse, die wir BoruvkaMST nennen . Lassen Sie uns zunächst einige Instanzvariablen deklarieren:

public class BoruvkaMST { private static MutableValueGraph mst = ValueGraphBuilder.undirected().build(); private static int totalWeight; } 

Wie wir sehen können, verwenden wir hier MutableValueGraph , um die MST darzustellen.

Zweitens definieren wir einen Konstruktor, in dem die ganze Magie geschieht. Es braucht ein Argument - das Diagramm, das wir zuvor erstellt haben.

Als erstes wird ein UnionFind der Eckpunkte des Eingabediagramms initialisiert . Anfangs sind alle Eckpunkte ihre eigenen Eltern mit einem Rang von 0:

public BoruvkaMST(MutableValueGraph graph) { int size = graph.nodes().size(); UnionFind uf = new UnionFind(size); 

Als Nächstes erstellen wir eine Schleife, die die Anzahl der Iterationen definiert, die zum Erstellen des MST erforderlich sind - höchstens log V-mal oder bis wir V-1-Kanten haben, wobei V die Anzahl der Scheitelpunkte ist:

for (int t = 1; t < size && mst.edges().size() < size - 1; t = t + t) { EndpointPair[] closestEdgeArray = new EndpointPair[size]; 

Hier initialisieren wir auch ein Array von Kanten, nextEdgeArray , um die nächsten Kanten mit geringerer Gewichtung zu speichern.

Danach definieren wir eine innere for- Schleife, die über alle Kanten des Diagramms iteriert, um unser nächstgelegenes EdgeArray zu füllen .

Wenn die übergeordneten Elemente der beiden Scheitelpunkte identisch sind, handelt es sich um denselben Baum, und wir fügen ihn nicht dem Array hinzu. Andernfalls vergleichen wir das Gewicht der aktuellen Kante mit dem Gewicht der Kanten der übergeordneten Scheitelpunkte. Wenn es kleiner ist, fügen wir es dem nächsten EdgeArray hinzu:

for (EndpointPair edge : graph.edges()) { int u = edge.nodeU(); int v = edge.nodeV(); int uParent = uf.find(u); int vParent = uf.find(v); if (uParent == vParent) { continue; } int weight = graph.edgeValueOrDefault(u, v, 0); if (closestEdgeArray[uParent] == null) { closestEdgeArray[uParent] = edge; } if (closestEdgeArray[vParent] == null) { closestEdgeArray[vParent] = edge; } int uParentWeight = graph.edgeValueOrDefault(closestEdgeArray[uParent].nodeU(), closestEdgeArray[uParent].nodeV(), 0); int vParentWeight = graph.edgeValueOrDefault(closestEdgeArray[vParent].nodeU(), closestEdgeArray[vParent].nodeV(), 0); if (weight < uParentWeight) { closestEdgeArray[uParent] = edge; } if (weight < vParentWeight) { closestEdgeArray[vParent] = edge; } } 

Then, we'll define a second inner loop to create a tree. We'll add edges from the above step to this tree without adding the same edge twice. Additionally, we'll perform a union on our UnionFind to derive and store parents and ranks of the newly created trees' vertices:

for (int i = 0; i < size; i++) { EndpointPair edge = closestEdgeArray[i]; if (edge != null) { int u = edge.nodeU(); int v = edge.nodeV(); int weight = graph.edgeValueOrDefault(u, v, 0); if (uf.find(u) != uf.find(v)) { mst.putEdgeValue(u, v, weight); totalWeight += weight; uf.union(u, v); } } } 

After repeating these steps at most log V times or until we have V-1 edges, the resulting tree is our MST.

4. Testing

Finally, let's see a simple JUnit to verify our implementation:

@Test public void givenInputGraph_whenBoruvkaPerformed_thenMinimumSpanningTree() { BoruvkaMST boruvkaMST = new BoruvkaMST(graph); MutableValueGraph mst = boruvkaMST.getMST(); assertEquals(30, boruvkaMST.getTotalWeight()); assertEquals(4, mst.getEdgeCount()); } 

As we can see, we got the MST with a weight of 30 and 4 edges, the same as the pictorial example.

5. Conclusion

In diesem Tutorial haben wir die Java-Implementierung des Boruvka-Algorithmus gesehen. Seine zeitliche Komplexität ist O (E log V), wobei E die Anzahl der Kanten und V die Anzahl der Eckpunkte ist .

Wie immer ist der Quellcode über GitHub verfügbar.