In diesem Artikel werden wir den Kruskal-Algorithmus diskutieren. Hier werden wir auch die Komplexität, Funktionsweise, Beispiele und Implementierung des Kruskal-Algorithmus sehen.
Bevor wir uns jedoch direkt dem Algorithmus zuwenden, sollten wir zunächst die Grundbegriffe wie Spanning Tree und Minimum Spanning Tree verstehen.
Spannender Baum - Ein Spanning Tree ist der Teilgraph eines ungerichteten zusammenhängenden Graphen.
Minimaler Spannbaum - Der minimale Spannbaum kann als der Spannbaum definiert werden, in dem die Summe der Kantengewichte minimal ist. Das Gewicht des Spannbaums ist die Summe der Gewichte, die den Kanten des Spannbaums gegeben werden.
Beginnen wir nun mit dem Hauptthema.
Kruskals Algorithmus wird verwendet, um den minimalen Spannbaum für einen verbundenen gewichteten Graphen zu finden. Das Hauptziel des Algorithmus besteht darin, die Teilmenge der Kanten zu finden, mit deren Hilfe wir jeden Scheitelpunkt des Graphen durchlaufen können. Es folgt dem Greedy-Ansatz, der in jeder Phase eine optimale Lösung findet, anstatt sich auf ein globales Optimum zu konzentrieren.
Wie funktioniert Kruskals Algorithmus?
Im Kruskal-Algorithmus beginnen wir mit den Kanten mit dem niedrigsten Gewicht und fügen so lange Kanten hinzu, bis das Ziel erreicht ist. Die Schritte zur Implementierung des Kruskal-Algorithmus sind wie folgt aufgeführt:
- Sortieren Sie zunächst alle Kanten von niedrig nach hoch.
- Nehmen Sie nun die Kante mit dem geringsten Gewicht und fügen Sie sie an den Spannbaum an. Wenn die hinzuzufügende Kante einen Zyklus erzeugt, verwerfen Sie die Kante.
- Fügen Sie die Kanten weiter hinzu, bis wir alle Eckpunkte erreicht haben und ein minimaler Spannbaum erstellt ist.
Die Anwendungen des Kruskal-Algorithmus sind:
- Der Algorithmus von Kruskal kann zur Planung der elektrischen Leitungen zwischen Städten verwendet werden.
- Damit können LAN-Verbindungen aufgebaut werden.
Beispiel für Kruskals Algorithmus
Sehen wir uns nun die Funktionsweise des Kruskal-Algorithmus anhand eines Beispiels an. Anhand eines Beispiels lässt sich Kruskals Algorithmus leichter verstehen.
Angenommen, ein gewichteter Graph ist -
Das Gewicht der Kanten des obigen Diagramms ist in der folgenden Tabelle angegeben:
| Rand | AB | Wechselstrom | ANZEIGE | ABER | Chr | CD | VON |
| Gewicht | 1 | 7 | 10 | 5 | 3 | 4 | 2 |
Sortieren Sie nun die oben angegebenen Kanten in aufsteigender Reihenfolge ihrer Gewichte.
| Rand | AB | VON | Chr | CD | ABER | Wechselstrom | ANZEIGE |
| Gewicht | 1 | 2 | 3 | 4 | 5 | 7 | 10 |
Beginnen wir nun mit der Konstruktion des minimalen Spannbaums.
Java-Binärbaum
Schritt 1 - Fügen Sie zunächst die Kante hinzu AB mit Gewicht 1 zum MST.
Schritt 2 - Fügen Sie die Kante hinzu VON mit Gewicht 2 zum MST, da es den Zyklus nicht erstellt.
Schritt 3 - Fügen Sie die Kante hinzu Chr mit Gewicht 3 zum MST, da es keinen Zyklus oder keine Schleife erzeugt.
Schritt 4 - Wählen Sie nun die Kante aus CD mit Gewicht 4 zum MST, da es den Zyklus nicht bildet.
Schritt 5 – Wählen Sie danach die Kante aus ABER mit Gewicht 5. Durch das Einbeziehen dieser Kante wird der Zyklus erstellt, also verwerfen Sie ihn.
Schritt 6 – Wählen Sie die Kante Wechselstrom mit Gewicht 7. Durch das Einbeziehen dieser Kante wird der Zyklus erstellt, also verwerfen Sie ihn.
Schritt 7 – Wählen Sie die Kante ANZEIGE mit Gewicht 10. Durch das Einbeziehen dieser Kante wird auch der Zyklus erstellt, also verwerfen Sie ihn.
Der endgültige minimale aufspannende Baum, der aus dem gegebenen gewichteten Graphen unter Verwendung des Kruskal-Algorithmus erhalten wird, ist also –
Die Kosten des MST betragen = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Nun ist die Anzahl der Kanten im obigen Baum gleich der Anzahl der Eckpunkte minus 1. Der Algorithmus hört hier also auf.
Algorithmus
Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END
Komplexität des Kruskal-Algorithmus
Sehen wir uns nun die zeitliche Komplexität des Kruskal-Algorithmus an.
Die Zeitkomplexität des Kruskal-Algorithmus beträgt O(E logE) oder O(V logV), wobei E die Zahl ist. der Kanten und V ist die Anzahl der Kanten. von Eckpunkten.
Implementierung des Kruskal-Algorithmus
Sehen wir uns nun die Implementierung des Kruskal-Algorithmus an.
Programm: Schreiben Sie ein Programm zur Implementierung des Kruskal-Algorithmus in C++.
#include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes >> edges; for(int i = 0;i <edges;++i) { cout<> x >> y >> weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout <<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>