minimum spanning tree tutorial
In diesem C ++ - Tutorial wird erklärt, was ein Minimum Spanning Tree (MST) ist, zusammen mit den Algorithmen von Prim und Kruskal, um MST in einem Diagramm und seinen Anwendungen zu finden:
Ein Spanning Tree kann als Teilmenge eines Diagramms definiert werden, das aus allen Scheitelpunkten besteht, die minimal mögliche Kanten abdecken, und keinen Zyklus hat. Spanning Tree kann nicht getrennt werden.
Jeder verbundene und ungerichtete Graph hat mindestens einen Spanning Tree. Ein nicht verbundener Graph hat keinen Spanning Tree, da nicht alle Scheitelpunkte eingeschlossen werden können.
=> Hier finden Sie Informationen zur vollständigen Liste der C ++ - Tutorials.
Was du lernen wirst:
Spanning Tree in C ++
Betrachten Sie das folgende zusammenhängende Diagramm.
Wie oben gezeigt, haben wir für den gegebenen verbundenen Graphen, der 3 Eckpunkte enthält, drei überspannende Bäume. Wenn N die Anzahl der Knoten in einem Diagramm ist, hat ein vollständig verbundener Diagramm im Allgemeinen das Maximum N.N-2Anzahl der überspannenden Bäume. Somit hat es in dem obigen Diagramm N = 3 3(3-2)= 3 überspannende Bäume.
Einige der Eigenschaften des Spanning Tree sind unten aufgeführt:
- Ein verbundener Graph kann mehr als einen Spannbaum haben.
- Alle Spannbäume in einem Diagramm haben die gleiche Anzahl von Knoten und Kanten.
- Wenn wir eine Kante aus dem Spanning Tree entfernen, wird es minimal verbunden und wird das Diagramm getrennt.
- Wenn Sie dem Spanning Tree jedoch eine Kante hinzufügen, wird dies erreicht maximal azyklisch wodurch eine Schleife erzeugt wird.
- Ein Spanning Tree hat keine Schleife oder keinen Zyklus.
Was ist ein Minimum Spanning Tree (MST)?
Ein minimaler Spannbaum ist derjenige, der das geringste Gewicht unter allen anderen Spannbäumen eines verbundenen gewichteten Graphen enthält. Es kann mehr als einen minimalen Spannbaum für ein Diagramm geben.
Es gibt zwei gängigste Algorithmen, mit denen der minimale Spannbaum in einem Diagramm ermittelt wird.
Sie beinhalten:
- Kruskals Algorithmus
- Prims Algorithmus
Lassen Sie uns diese beiden Algorithmen diskutieren!
Kruskals Algorithmus
Der Kruskal-Algorithmus ist ein Algorithmus zum Finden des MST in einem verbundenen Graphen.
Kruskals Algorithmus findet eine Teilmenge eines Graphen G, so dass:
- Es bildet einen Baum mit jedem Scheitelpunkt darin.
- Die Summe der Gewichte ist das Minimum unter allen Spannbäumen, die aus diesem Diagramm gebildet werden können.
Die Reihenfolge der Schritte für den Kruskal-Algorithmus ist wie folgt:
- Sortieren Sie zuerst alle Kanten vom niedrigsten zum höchsten Gewicht.
- Nehmen Sie die Kante mit dem geringsten Gewicht und fügen Sie sie dem Spannbaum hinzu. Wenn der Zyklus erstellt wurde, verwerfen Sie die Kante.
- Fügen Sie weitere Kanten wie in Schritt 1 hinzu, bis alle Scheitelpunkte berücksichtigt sind.
Pseudocode für Kruskals Algorithmus
Unten ist der Pseudocode für den Kruskal-Algorithmus angegeben
Lassen Sie uns nun die Darstellung des Kruskal-Algorithmus sehen.
Jetzt wählen wir die Kante mit dem geringsten Gewicht, die 2-4 ist.
Wählen Sie als nächstes die nächst kürzere Kante 2-3.
Dann wählen wir die nächste Kante mit der kürzesten Kante und das erzeugt keinen Zyklus, d. H. 0-3
beste Weg, um YouTube in mp4 zu konvertieren
Der nächste Schritt besteht darin, die kürzeste Kante auszuwählen, damit sie keinen Zyklus bildet. Dies ist 0-1.
Wie wir sehen können, haben wir alle Eckpunkte abgedeckt und haben hier einen Spannbaum mit minimalen Kosten.
Als nächstes werden wir den Kruskal-Algorithmus mit C ++ implementieren.
#include #include #include using namespace std; #define graph_edge pair class Graph { private: int V; // number of nodes in graph vector> G; // vector for graph vector> T; // vector for mst int *parent; public: Graph(int V); void AddEdge(int u, int v, int wt); int find_set(int i); void union_set(int u, int v); void kruskal_algorithm(); void display_mst(); }; Graph::Graph(int V) { parent = new int(V); for (int i = 0; i Ausgabe:
Der Minimum Spanning Tree (MST) nach Kruskals Algorithmus:
Kante: Gewicht
2 - 4: 1
2 - 3: 2
0 - 1: 3
0 - 3: 3
Beachten Sie, dass wir im Programm dasselbe Beispieldiagramm verwendet haben, das wir in der obigen Abbildung des Kruskal-Algorithmus verwendet haben. In dieser Implementierung verwenden wir zwei Vektoren; eine zum Speichern des Diagramms und eine zum Speichern des minimalen Spannbaums. Wir finden rekursiv die Kanten mit dem geringsten Gewicht und fügen sie dem MST-Vektor hinzu, bis alle Eckpunkte bedeckt sind.
Prims Algorithmus
Der Prim-Algorithmus ist ein weiterer Algorithmus, um das Minimum zu ermitteln, das sich über den Baum eines Graphen erstreckt. Im Gegensatz zum Kruskal-Algorithmus, der mit Diagrammkanten beginnt, beginnt der Prim-Algorithmus mit einem Scheitelpunkt. Wir beginnen mit einem Scheitelpunkt und fügen weiterhin Kanten mit dem geringsten Gewicht hinzu, bis alle Scheitelpunkte bedeckt sind.
Die Reihenfolge der Schritte für den Prim-Algorithmus ist wie folgt:
- Wählen Sie einen zufälligen Scheitelpunkt als Startscheitelpunkt und initialisieren Sie einen minimalen Spannbaum.
- Suchen Sie die Kanten, die mit anderen Scheitelpunkten verbunden sind. Suchen Sie die Kante mit minimalem Gewicht und fügen Sie sie dem Spannbaum hinzu.
- Wiederholen Sie Schritt 2, bis der Spannbaum erhalten ist.
Pseudocode für den Prim-Algorithmus
Lassen Sie uns nun eine Illustration für den Prim-Algorithmus sehen.
Dazu verwenden wir dasselbe Beispieldiagramm, das wir in der Illustration des Kruskal-Algorithmus verwendet haben.
Wählen wir Knoten 2 als zufälligen Scheitelpunkt.
Als nächstes wählen wir die Kante mit dem geringsten Gewicht aus 2. Wir wählen die Kante 2-4.
Als nächstes wählen wir einen anderen Scheitelpunkt aus, der sich noch nicht im Spanning Tree befindet. Wir wählen die Kante 2-3.
Wählen wir nun eine Kante mit dem geringsten Gewicht aus den obigen Eckpunkten aus. Wir haben Kante 3-0, die das geringste Gewicht hat.
Als nächstes wählen wir eine Kante mit dem geringsten Gewicht aus Scheitelpunkt 0. Dies ist die Kante 0-1.
Aus der obigen Abbildung geht hervor, dass wir jetzt alle Scheitelpunkte im Diagramm abgedeckt und einen vollständigen Spannbaum mit minimalen Kosten erhalten haben.
Lassen Sie uns nun den Prim-Algorithmus in C ++ implementieren.
Beachten Sie, dass wir auch in diesem Programm das obige Beispieldiagramm als Eingabe verwendet haben, damit wir die vom Programm angegebene Ausgabe zusammen mit der Abbildung vergleichen können.
Das Programm ist unten angegeben:
#include #include using namespace std; #define INF 9999 // graph contains 5 vertices #define V 5 // an array G that stores adjacency matrix for input graph int G(V)(V) = { {0, 3, 0, 3, 0}, {3, 0, 0, 0, 4}, {0, 0, 0, 2, 1}, {3, 3, 2, 0, 0}, {0, 4, 1, 0, 0}}; int main () { int num_edge; // number of edge // mst_vertex - array to track vertices selected for spanning tree int mst_vertex(V); // set selected false initially memset (mst_vertex, false, sizeof (mst_vertex)); // set number of edge to 0 num_edge = 0; //let 0th vertex be the first to be selected mst_vertex(0) = true; int x; // row int y; // col // print details of MST cout<<'The Minimum Spanning Tree as per Prim's Algorithm:'< G(i)(j)) { min = G(i)(j); x = i; y = j; } } } } } cout << x << ' - ' << y << ' : ' << G(x)(y); cout << endl; mst_vertex(y) = true; num_edge++; } return 0; } Ausgabe:
Der minimale Spanning Tree gemäß dem Prim-Algorithmus:
Kante: Gewicht
0 - 1: 3
0 - 3: 3
3 - 2: 2
2 - 4: 1
Anwendungen von Spanning Tree
Einige der Anwendungen von Minimum Spanning Trees sind wie folgt:
# 1) Einrichtung des Kommunikationsnetzwerks: Wenn wir ein Kommunikationsnetzwerk über Kommunikationsverbindungen einrichten möchten, werden die Kosten für die Einrichtung von Kommunikationsverbindungen zwischen zwei Punkten am besten mithilfe eines MST ermittelt.
# 2) Clusteranalyse: Es kann verwendet werden, um das K-Clustering-Problem zu lösen, indem ein minimaler Spanning Tree gefunden und die teuersten k-1-Kanten gelöscht werden.
# 3) Ausbau von Straßen- / Schienennetzen: Wenn wir verschiedene Straßen- oder Schienennetze zwischen oder innerhalb von Städten verlegen, sind die Kosten des Projekts ein sehr wichtiger Faktor. Wir können den besten Weg mit minimalen Kosten finden, indem wir minimale Spannbäume verwenden.
# 4) Planung von Wohneinrichtungen: Einrichtungen wie Strom, Wasser, Abwasser usw., die für eine Reihe von Häusern bereitgestellt werden sollen, müssen ebenfalls zu optimalen Kosten angeboten werden, und dies erfolgt mithilfe eines MST.
# 5) Lösung des Problems des reisenden Verkäufers: Wir können einen MST verwenden, um das Problem des Handlungsreisenden zu lösen, bei dem jeder Punkt mindestens einmal besucht werden muss.
Fazit
Der minimale Spannbaum ist die Teilmenge des Graphen g, und diese Teilmenge enthält alle Eckpunkte des Graphen, und die Gesamtkosten der Kanten, die die Eckpunkte verbinden, sind minimal.
Wir haben zwei Algorithmen diskutiert, d. H. Kruskals und Prims, um den minimalen Spannbaum aus dem Diagramm zu ermitteln. Die Anwendungen des Spanning Tree wurden auch hier in diesem Tutorial erklärt.
=> Schauen Sie sich hier die besten C ++ - Schulungsanleitungen an.
Literatur-Empfehlungen
- Java Reflection Tutorial mit Beispielen
- B-Baum- und B + -Baum-Datenstruktur in C ++
- Python DateTime Tutorial mit Beispielen
- Bugzilla Tutorial: Praktisches Tutorial zum Fehlermanagement-Tool
- Datenstruktur des Binärbaums in C ++
- 20+ MongoDB Tutorial für Anfänger: Kostenloser MongoDB Kurs
- MongoDB Sharding Tutorial mit Beispiel
- MongoDB Tutorial zum Erstellen einer Datenbank
