Prims Algorithmus mit einer Java-Implementierung

1. Einleitung

In diesem Tutorial lernen wir zunächst, wie viele Spannbäume minimal sind. Danach werden wir den Prim-Algorithmus verwenden, um einen zu finden.

2. Minimum Spanning Tree

Ein Minimum Spanning Tree (MST) ist ein gewichteter, ungerichteter, verbundener Graph, dessen Gesamtkantengewicht durch Entfernen schwererer Kanten minimiert wurde . Mit anderen Worten, wir behalten alle Eckpunkte des Diagramms bei, können jedoch einige Kanten entfernen, sodass die Summe aller Kanten minimal ist.

Wir beginnen mit einem gewichteten Diagramm, da es keinen Sinn macht, das Gesamtkantengewicht zu minimieren, wenn diese Kanten überhaupt kein Gewicht haben. Schauen wir uns ein Beispieldiagramm an:

Das obige Diagramm ist ein gewichtetes, ungerichtetes, verbundenes Diagramm. Hier ist eine MST dieses Diagramms:

Ein MST eines Diagramms ist jedoch nicht eindeutig. Wenn ein Graph mehr als eine MST hat, hat jede MST das gleiche Gesamtkantengewicht.

3. Prims Algorithmus

Der Algorithmus von Prim verwendet einen gewichteten, ungerichteten, verbundenen Graphen als Eingabe und gibt einen MST dieses Graphen als Ausgabe zurück .

Es funktioniert gierig . Im ersten Schritt wird ein beliebiger Scheitelpunkt ausgewählt. Danach fügt jeder neue Schritt dem bisher erstellten Baum den nächsten Scheitelpunkt hinzu, bis kein getrennter Scheitelpunkt mehr vorhanden ist.

Lassen Sie uns den Prim-Algorithmus Schritt für Schritt in diesem Diagramm ausführen:

Angenommen, der beliebige Scheitelpunkt zum Starten des Algorithmus ist B, dann haben wir drei Möglichkeiten: A, C und E. Die entsprechenden Gewichte der Kanten sind 2, 2 und 5, daher ist das Minimum 2. In diesem Fall haben wir zwei Kanten mit einem Gewicht von 2, sodass wir eine von beiden auswählen können (es spielt keine Rolle, welche). Wählen wir A:

Jetzt haben wir einen Baum mit zwei Eckpunkten A und B. Wir können alle noch nicht hinzugefügten Kanten von A oder B auswählen, die zu einem nicht hinzugefügten Eckpunkt führen. Wir können also AC, BC oder BE auswählen.

Prims Algorithmus wählt das Minimum, nämlich 2 oder BC:

Jetzt haben wir einen Baum mit drei Eckpunkten und drei möglichen Kanten, um vorwärts zu kommen: CD, CE oder BE. AC ist nicht enthalten, da dem Baum kein neuer Scheitelpunkt hinzugefügt wird. Das Mindestgewicht unter diesen drei ist 1.

Es gibt jedoch zwei Kanten, die beide 1 wiegen. Folglich wählt der Prim-Algorithmus in diesem Schritt eine davon aus (wiederum spielt keine Rolle, welche):

Es gibt nur noch einen Scheitelpunkt zum Verbinden, sodass wir zwischen CE und BE wählen können. Das Mindestgewicht, mit dem unser Baum verbunden werden kann, beträgt 1, und der Prim-Algorithmus wählt es aus:

Da jetzt alle Eckpunkte des Eingabegraphen im Ausgabebaum vorhanden sind, endet der Prim-Algorithmus. Daher ist dieser Baum eine MST des Eingabegraphen.

4. Implementierung

Scheitelpunkte und Kanten bilden Diagramme, daher benötigen wir eine Datenstruktur, um diese Elemente zu speichern. Erstellen wir die Klasse Edge :

public class Edge { private int weight; private boolean isIncluded = false; }

Jede Kante muss eine Gewichtung haben, da der Prim-Algorithmus für gewichtete Diagramme arbeitet. isIncluded zeigt an, ob die Kante im minimalen Spanning Tree vorhanden ist oder nicht.

Fügen wir nun die Vertex- Klasse hinzu:

public class Vertex { private String label = null; private Map edges = new HashMap(); private boolean isVisited = false; }

Jeder Vertex kann optional eine Beschriftung haben . Wir verwenden die Kantenabbildung , um Verbindungen zwischen Scheitelpunkten zu speichern. Schließlich zeigt isVisited , ob der Scheitelpunkt bisher vom Prim-Algorithmus besucht wurde oder nicht.

Erstellen wir unsere Prim- Klasse, in der wir die Logik implementieren:

public class Prim { private List graph; }

Eine Liste von Scheitelpunkten reicht aus, um das gesamte Diagramm zu speichern, da wir in jedem Scheitelpunkt eine Karte haben , um alle Verbindungen zu identifizieren. In Prim erstellen wir eine run () -Methode:

public void run() { if (graph.size() > 0) { graph.get(0).setVisited(true); } while (isDisconnected()) { Edge nextMinimum = new Edge(Integer.MAX_VALUE); Vertex nextVertex = graph.get(0); for (Vertex vertex : graph) { if (vertex.isVisited()) { Pair candidate = vertex.nextMinimum(); if (candidate.getValue().getWeight() < nextMinimum.getWeight()) { nextMinimum = candidate.getValue(); nextVertex = candidate.getKey(); } } } nextMinimum.setIncluded(true); nextVertex.setVisited(true); } }

Wir beginnen damit, das erste Element des Listendiagramms als besucht festzulegen. Das erste Element kann einer der Eckpunkte sein, abhängig von der Reihenfolge, in der sie der Liste hinzugefügt wurden. isDisconnected () gibt true zurück , wenn ein Vertex bisher nicht besucht wurde:

private boolean isDisconnected() { for (Vertex vertex : graph) { if (!vertex.isVisited()) { return true; } } return false; }

Während der minimale Spannbaum TreeDisconnected () ist , durchlaufen wir die bereits besuchten Scheitelpunkte und finden die Kante mit dem minimalen Gewicht als Kandidaten für nextVertex:

public Pair nextMinimum() { Edge nextMinimum = new Edge(Integer.MAX_VALUE); Vertex nextVertex = this; Iterator
    
      it = edges.entrySet() .iterator(); while (it.hasNext()) { Map.Entry pair = it.next(); if (!pair.getKey().isVisited()) { if (!pair.getValue().isIncluded()) { if (pair.getValue().getWeight() < nextMinimum.getWeight()) { nextMinimum = pair.getValue(); nextVertex = pair.getKey(); } } } } return new Pair(nextVertex, nextMinimum); }
    

We find the minimum of all candidates in the main loop and store it in nextVertex. Then, we set nextVertex as visited. The loop goes on until all vertices are visited.

At the end, each Edge with isIncluded equal to true is present.

Note that since nextMinimum() iterates through the edges, the time complexity of this implementation is O(V2). If we store the edges in a priority queue (sorted by weight) instead, the algorithm will perform in O(E log V).

5. Testing

Okay, so now that we've got some code, let's test it with a real example. First, we construct our graph:

public static List createGraph() { List graph = new ArrayList(); Vertex a = new Vertex("A"); ... Vertex e = new Vertex("E"); Edge ab = new Edge(2); a.addEdge(b, ab); b.addEdge(a, ab); ... Edge ce = new Edge(1); c.addEdge(e, ce); e.addEdge(c, ce); graph.add(a); ... graph.add(e); return graph; }

Der Konstruktor der Prim- Klasse nimmt es und speichert es in der Klasse. Wir können das Eingabediagramm mit der originalGraphToString () -Methode drucken :

Prim prim = new Prim(createGraph()); System.out.println(prim.originalGraphToString());

Unser Beispiel wird Folgendes ausgeben:

A --- 2 --- B A --- 3 --- C B --- 5 --- E B --- 2 --- C C --- 1 --- E C --- 1 --- D

Jetzt führen wir den Prim-Algorithmus aus und drucken den resultierenden MST mit der Methode minimumSpanningTreeToString () :

prim.run(); prim.resetPrintHistory(); System.out.println(prim.minimumSpanningTreeToString());

Zum Schluss drucken wir unser MST aus:

A --- 2 --- B B --- 2 --- C C --- 1 --- E C --- 1 --- D

6. Fazit

In diesem Artikel haben wir erfahren, wie der Prim-Algorithmus einen minimalen Spannbaum eines Graphen findet. Der Code ist auf GitHub verfügbar.