Ein minimaler Spannbaum (MST) oder Minimum Weight Spanning Tree für einen gewichteten, verbundenen, ungerichteten Graphen ist ein Spanning Tree mit einem Gewicht, das kleiner oder gleich dem Gewicht jedes anderen Spanning Tree ist. Weitere Informationen zum Minimum Spanning Tree finden Sie unter Dieser Artikel .
Einführung in Kruskals Algorithmus:
Hier werden wir diskutieren Kruskals Algorithmus um den MST eines gegebenen gewichteten Graphen zu finden.
Sortieren Sie im Kruskal-Algorithmus alle Kanten des gegebenen Graphen in aufsteigender Reihenfolge. Anschließend werden im MST weiterhin neue Kanten und Knoten hinzugefügt, wenn die neu hinzugefügte Kante keinen Zyklus bildet. Zuerst wird die minimal gewichtete Kante und zuletzt die maximal gewichtete Kante ausgewählt. Wir können also sagen, dass es in jedem Schritt eine lokal optimale Wahl trifft, um die optimale Lösung zu finden. Daher ist dies ein Im Folgenden finden Sie die Schritte zum Finden von MST mithilfe des Kruskal-Algorithmus:
- Sortieren Sie alle Kanten in nicht abnehmender Reihenfolge ihres Gewichts.
- Wählen Sie die kleinste Kante. Überprüfen Sie, ob es mit dem bisher gebildeten Spanning Tree einen Zyklus bildet. Wenn der Kreis nicht gebildet wird, schließen Sie diese Kante ein. Andernfalls werfen Sie es weg.
- Wiederholen Sie Schritt 2, bis der Spannbaum (V-1) Kanten enthält.
Schritt 2 nutzt die Union-Find-Algorithmus Zyklen zu erkennen.
Daher empfehlen wir als Voraussetzung, den folgenden Beitrag zu lesen.
- Union-Find-Algorithmus | Satz 1 (Zyklus in einem Diagramm erkennen)
- Union-Find-Algorithmus | Satz 2 (Vereinigung nach Rang und Pfadkomprimierung)
Kruskals Algorithmus zur Ermittlung des Spannbaums mit minimalen Kosten verwendet den Greedy-Ansatz. Die gierige Wahl besteht darin, die kleinste Gewichtskante auszuwählen, die im bisher konstruierten MST keinen Zyklus verursacht. Lassen Sie es uns anhand eines Beispiels verstehen:
Illustration:
Nachfolgend finden Sie eine Darstellung des oben genannten Ansatzes:
Eingabediagramm:
string a intDer Graph enthält 9 Eckpunkte und 14 Kanten. Der minimal gebildete Spannbaum hat also (9 – 1) = 8 Kanten.
Nach dem Sortieren:
Gewicht Quelle Ziel 1 7 6 2 8 2 2 6 5 4 0 1 4 2 5 6 8 6 7 2 3 7 7 8 8 0 7 8 1 2 9 3 4 10 5 4 elf 1 7 14 3 5 Wählen Sie nun nacheinander alle Kanten aus der sortierten Kantenliste aus
Schritt 1: Wählen Sie Kante 7-6. Es entsteht kein Kreislauf, schließen Sie ihn ein.
Fügen Sie Kante 7-6 im MST hinzu
Schritt 2: Pick-Edge 8-2. Es entsteht kein Kreislauf, schließen Sie ihn ein.
Fügen Sie Kante 8-2 im MST hinzu
Schritt 3: Schlagkante 6-5. Es entsteht kein Kreislauf, schließen Sie ihn ein.
Fügen Sie Kante 6-5 im MST hinzu
Schritt 4: Pick-Edge 0-1. Es entsteht kein Kreislauf, schließen Sie ihn ein.
Java-Typkonvertierung und -CastingFügen Sie Kante 0-1 im MST hinzu
Schritt 5: Wählen Sie Kante 2-5. Es entsteht kein Kreislauf, schließen Sie ihn ein.
Fügen Sie Kante 2-5 im MST hinzu
Schritt 6: Schlagkante 8-6. Da das Einbeziehen dieser Kante zum Zyklus führt, verwerfen Sie ihn. Schlagkante 2-3: Es entsteht kein Kreislauf, schließen Sie ihn ein.
Fügen Sie Kante 2-3 im MST hinzu
Schritt 7: Wählen Sie Kante 7-8. Da das Einbeziehen dieser Kante zum Zyklus führt, verwerfen Sie ihn. Wählen Sie Kante 0-7. Es entsteht kein Kreislauf, schließen Sie ihn ein.
Fügen Sie Kante 0-7 in MST hinzu
Schritt 8: Wählen Sie Kante 1-2. Da das Einbeziehen dieser Kante zum Zyklus führt, verwerfen Sie ihn. Wählen Sie Kante 3-4. Es entsteht kein Kreislauf, schließen Sie ihn ein.
Kante 3-4 im MST hinzufügen
Notiz: Da die Anzahl der im MST enthaltenen Kanten gleich (V – 1) ist, stoppt der Algorithmus hier
Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:
C++
// C++ program for the above approach> > #include> using> namespace> std;> > // DSU data structure> // path compression + rank by union> class> DSU {> >int>* parent;> >int>* rank;> > public>:> >DSU(>int> n)> >{> >parent =>new> int>[n];> >rank =>new> int>[n];> > >for> (>int> i = 0; i parent[i] = -1; rank[i] = 1; } } // Find function int find(int i) { if (parent[i] == -1) return i; return parent[i] = find(parent[i]); } // Union function void unite(int x, int y) { int s1 = find(x); int s2 = find(y); if (s1 != s2) { if (rank[s1] parent[s1] = s2; } else if (rank[s1]>rank[s2]) { parent[s2] = s1; } else { parent[s2] = s1; Rang[s1] += 1; } } } }; Klasse Graph { vectorint>> Edgelist; im Fernsehen; public: Graph(int V) { this->V = V; } // Funktion zum Hinzufügen einer Kante in einem Diagramm void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() { // Alle Kanten sortieren sort(edgelist.begin(), edgelist.end()); // Initialisiere die DSU DSU s(V); int ans = 0; cout<< 'Following are the edges in the ' 'constructed MST' << endl; for (auto edge : edgelist) { int w = edge[0]; int x = edge[1]; int y = edge[2]; // Take this edge in MST if it does // not forms a cycle if (s.find(x) != s.find(y)) { s.unite(x, y); ans += w; cout << x << ' -- ' << y << ' == ' << w << endl; } } cout << 'Minimum Cost Spanning Tree: ' << ans; } }; // Driver code int main() { Graph g(4); g.addEdge(0, 1, 10); g.addEdge(1, 3, 15); g.addEdge(2, 3, 4); g.addEdge(2, 0, 6); g.addEdge(0, 3, 5); // Function call g.kruskals_mst(); return 0; }> |
>
>
C
Zeichenfolge JSON Java
// C code to implement Kruskal's algorithm> > #include> #include> > // Comparator function to use in sorting> int> comparator(>const> void>* p1,>const> void>* p2)> {> >const> int>(*x)[3] = p1;> >const> int>(*y)[3] = p2;> > >return> (*x)[2] - (*y)[2];> }> > // Initialization of parent[] and rank[] arrays> void> makeSet(>int> parent[],>int> rank[],>int> n)> {> >for> (>int> i = 0; i parent[i] = i; rank[i] = 0; } } // Function to find the parent of a node int findParent(int parent[], int component) { if (parent[component] == component) return component; return parent[component] = findParent(parent, parent[component]); } // Function to unite two sets void unionSet(int u, int v, int parent[], int rank[], int n) { // Finding the parents u = findParent(parent, u); v = findParent(parent, v); if (rank[u] parent[u] = v; } else if (rank[u]>rank[v]) { parent[v] = u; } else { parent[v] = u; // Da der Rang zunimmt, wenn // die Ränge zweier Mengen gleich sind rank[u]++; } } // Funktion zum Finden des MST void kruskalAlgo(int n, int edge[n][3]) { // Zuerst sortieren wir das Kantenarray in aufsteigender Reihenfolge // damit wir auf Mindestabstände/Kosten zugreifen können qsort(edge , n, sizeof(edge[0]), Komparator); int parent[n]; int rank[n]; // Funktion zum Initialisieren von parent[] und rank[] makeSet(parent, rank, n); // Um die Mindestkosten zu speichern int minCost = 0; printf( 'Es folgen die Kanten im konstruierten MST
'); for (int i = 0; i int v1 = findParent(parent, edge[i][0]); int v2 = findParent(parent, edge[i][1]); int wt = edge[i][2] ; // Wenn die Eltern unterschiedlich sind, // bedeutet das, dass sie sich in unterschiedlichen Mengen befinden, also // sie vereinen if (v1 != v2) { unionSet(v1, v2, parent, rank, n); '%d -- %d == %d
', Edge[i][0], Edge[i][1], wt); printf('Minimum Cost Spanning Tree: %d); n', minCost); } // Treibercode int main() { int edge[5][3] = { { 0, 1, 10 }, { 0, 2, 6 }, { 0, 3, 5 } , { 1, 3, 15 }, { 2, 3, 4 } }; |
>
// Java program for Kruskal's algorithm>>import>java.util.ArrayList;>import>java.util.Comparator;>import>java.util.List;>>public>class>KruskalsMST {>>>// Defines edge structure>>static>class>Edge {>>int>src, dest, weight;>>>public>Edge(>int>src,>int>dest,>int>weight)>>{>>this>.src = src;>>this>.dest = dest;>>this>.weight = weight;>>}>>}>>>// Defines subset element structure>>static>class>Subset {>>int>parent, rank;>>>public>Subset(>int>parent,>int>rank)>>{>>this>.parent = parent;>>this>.rank = rank;>>}>>}>>>// Starting point of program execution>>public>static>void>main(String[] args)>>{>>int>V =>4>;>>List graphEdges =>new>ArrayList(>>List.of(>new>Edge(>0>,>1>,>10>),>new>Edge(>0>,>2>,>6>),>>new>Edge(>0>,>3>,>5>),>new>Edge(>1>,>3>,>15>),>>new>Edge(>2>,>3>,>4>)));>>>// Sort the edges in non-decreasing order>>// (increasing with repetition allowed)>>graphEdges.sort(>new>Comparator() {>>@Override>public>int>compare(Edge o1, Edge o2)>>{>>return>o1.weight - o2.weight;>>}>>});>>>kruskals(V, graphEdges);>>}>>>// Function to find the MST>>private>static>void>kruskals(>int>V, List edges)>>{>>int>j =>0>;>>int>noOfEdges =>0>;>>>// Allocate memory for creating V subsets>>Subset subsets[] =>new>Subset[V];>>>// Allocate memory for results>>Edge results[] =>new>Edge[V];>>>// Create V subsets with single elements>>for>(>int>i =>0>; i subsets[i] = new Subset(i, 0); } // Number of edges to be taken is equal to V-1 while (noOfEdges 1) { // Pick the smallest edge. And increment // the index for next iteration Edge nextEdge = edges.get(j); int x = findRoot(subsets, nextEdge.src); int y = findRoot(subsets, nextEdge.dest); // If including this edge doesn't cause cycle, // include it in result and increment the index // of result for next edge if (x != y) { results[noOfEdges] = nextEdge; union(subsets, x, y); noOfEdges++; } j++; } // Print the contents of result[] to display the // built MST System.out.println( 'Following are the edges of the constructed MST:'); int minCost = 0; for (int i = 0; i System.out.println(results[i].src + ' -- ' + results[i].dest + ' == ' + results[i].weight); minCost += results[i].weight; } System.out.println('Total cost of MST: ' + minCost); } // Function to unite two disjoint sets private static void union(Subset[] subsets, int x, int y) { int rootX = findRoot(subsets, x); int rootY = findRoot(subsets, y); if (subsets[rootY].rank subsets[rootY].parent = rootX; } else if (subsets[rootX].rank subsets[rootX].parent = rootY; } else { subsets[rootY].parent = rootX; subsets[rootX].rank++; } } // Function to find parent of a set private static int findRoot(Subset[] subsets, int i) { if (subsets[i].parent == i) return subsets[i].parent; subsets[i].parent = findRoot(subsets, subsets[i].parent); return subsets[i].parent; } } // This code is contributed by Salvino D'sa>>Deaktivieren Sie den Entwicklermodus>Python3
# Python program for Kruskal's algorithm to find># Minimum Spanning Tree of a given connected,># undirected and weighted graph>>># Class to represent a graph>class>Graph:>>>def>__init__(>self>, vertices):>>self>.V>=>vertices>>self>.graph>=>[]>>># Function to add an edge to graph>>def>addEdge(>self>, u, v, w):>>self>.graph.append([u, v, w])>>># A utility function to find set of an element i>># (truly uses path compression technique)>>def>find(>self>, parent, i):>>if>parent[i] !>=>i:>>># Reassignment of node's parent>># to root node as>># path compression requires>>parent[i]>=>self>.find(parent, parent[i])>>return>parent[i]>>># A function that does union of two sets of x and y>># (uses union by rank)>>def>union(>self>, parent, rank, x, y):>>># Attach smaller rank tree under root of>># high rank tree (Union by Rank)>>if>rank[x] parent[x] = y elif rank[x]>rank[y]: parent[y] = x # Wenn die Ränge gleich sind, dann machen Sie einen als Wurzel # und erhöhen Sie seinen Rang um eins else: parent[y] = x rank[x] += 1 # Die zu konstruierende Hauptfunktion MST # unter Verwendung des Kruskal-Algorithmus def KruskalMST(self): # Dies speichert das resultierende MST-Ergebnis = [] # Eine Indexvariable, die für sortierte Kanten verwendet wird i = 0 # Eine Indexvariable, die für result[] e = 0 verwendet wird # Sortiere alle Kanten in # nicht absteigender Reihenfolge ihrer # Gewichtung self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] # Erstelle V-Teilmengen mit einzelnen Elementen für Knoten im Bereich (self.V): parent.append(node) rank.append(0) # Anzahl der zu nehmenden Kanten ist kleiner als V-1, während e>>C#
Java-Substring-Methode
// C# Code for the above approach>>using>System;>>class>Graph {>>>// A class to represent a graph edge>>class>Edge : IComparable {>>public>int>src, dest, weight;>>>// Comparator function used for sorting edges>>// based on their weight>>public>int>CompareTo(Edge compareEdge)>>{>>return>this>.weight - compareEdge.weight;>>}>>}>>>// A class to represent>>// a subset for union-find>>public>class>subset {>>public>int>parent, rank;>>};>>>// V->NEIN. der Eckpunkte & E->Anzahl der Kanten>>int>V, E;>>>// Collection of all edges>>Edge[] edge;>>>// Creates a graph with V vertices and E edges>>Graph(>int>v,>int>e)>>{>>V = v;>>E = e;>>edge =>new>Edge[E];>>for>(>int>i = 0; i edge[i] = new Edge(); } // A utility function to find set of an element i // (uses path compression technique) int find(subset[] subsets, int i) { // Find root and make root as // parent of i (path compression) if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } // A function that does union of // two sets of x and y (uses union by rank) void Union(subset[] subsets, int x, int y) { int xroot = find(subsets, x); int yroot = find(subsets, y); // Attach smaller rank tree under root of // high rank tree (Union by Rank) if (subsets[xroot].rank subsets[xroot].parent = yroot; else if (subsets[xroot].rank>subsets[yroot].rank) subsets[yroot].parent = xroot; // Wenn die Ränge gleich sind, dann mache einen als Root // und erhöhe seinen Rang um eins else { subsets[yroot].parent = xroot; Teilmengen[xroot].rank++; } } // Die Hauptfunktion zum Erstellen von MST // unter Verwendung des Kruskal-Algorithmus void KruskalMST() { // Dies speichert // das resultierende MST Edge[] result = new Edge[V]; // Eine Indexvariable, die für result[] verwendet wird int e = 0; // Eine Indexvariable, die für sortierte Kanten verwendet wird int i = 0; for (i = 0; i result[i] = new Edge(); // Sortieren Sie alle Kanten in nicht abnehmender // Reihenfolge ihres Gewichts. Wenn es uns nicht erlaubt ist //, den gegebenen Graphen zu ändern, können wir ihn erstellen // eine Kopie des Kantenarrays Array.Sort(edge); // Speicher für die Erstellung von V-Teilmengen reservieren subset[] subsets = new subset[V] for (i = 0; i subsets[i] = new subset() ; // V Teilmengen mit einzelnen Elementen erstellen for (int v = 0; v subsets[v].parent = v; subsets[v].rank = 0; } i = 0; // Anzahl der zu nehmenden Kanten ist gleich zu V-1 while (e // Die kleinste Kante auswählen. Und // den Index für die nächste Iteration erhöhen Edge next_edge = new Edge(); next_edge = edge[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest); // Wenn die Einbeziehung dieser Kante keinen Zyklus verursacht, // füge sie in das Ergebnis ein und erhöhe den Index // des Ergebnisses für die nächste Kante if (x != y) { result[e++] = next_edge; Union(subsets, x, y); } } // Den Inhalt von result[] ausgeben, um // das erstellte MST anzuzeigen. Console.WriteLine('Folgend sind die Kanten in ' + ' das konstruierte MST'); int MinimumCost = 0; for (i = 0; i Console.WriteLine(result[i].src + ' -- ' + result[i].dest + ' == ' + result[i].weight); MinimumCost += result[i].weight; } Console.WriteLine('Minimum Cost Spanning Tree: ' + minimumCost); // Treibercode public static void Main(String[] args) { int V = 4; int E = 5; Graph graph = new Graph(V, E); // add edge 0-1 graph.edge[0].dest = 1; graph.edge[0].weight = 10; // Kante 0-2 hinzufügen graph.edge[1].src = 0; graph.edge[1].dest = 6 ; // Kante 0-3 hinzufügen graph.edge[2].src = 0; graph.edge[2].weight = 5; // Kante 1-3 hinzufügen Edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 15; // Kante 2-3 hinzufügen graph.edge[4].src = 2; .edge[4].dest = 3; graph.edge[4].weight = 4; // Funktionsaufruf graph.KruskalMST(); } // Dieser Code wurde von Aakash Hasija beigesteuert>>>Javascript
>// JavaScript implementation of the krushkal's algorithm.>>function>makeSet(parent,rank,n)>{>>for>(let i=0;i { parent[i]=i; rank[i]=0; } } function findParent(parent,component) { if(parent[component]==component) return component; return parent[component] = findParent(parent,parent[component]); } function unionSet(u, v, parent, rank,n) { //this function unions two set on the basis of rank //as shown below u=findParent(parent,u); v=findParent(parent,v); if(rank[u] { parent[u]=v; } else if(rank[u] { parent[v]=u; } else { parent[v]=u; rank[u]++;//since the rank increases if the ranks of two sets are same } } function kruskalAlgo(n, edge) { //First we sort the edge array in ascending order //so that we can access minimum distances/cost edge.sort((a, b)=>{ return a[2] - b[2]; }) //Eingebaute Schnellsortierfunktion ist in stdlib.h enthalten //gehe zu https://www.techcodeview.com Das Sortieren von Kanten dauert O(E * logE) Zeit. Nach dem Sortieren durchlaufen wir alle Kanten und wenden den Find-Union-Algorithmus an. Die Such- und Vereinigungsoperationen können höchstens O(logV) Zeit in Anspruch nehmen. Die Gesamtkomplexität beträgt also O(E * logE + E * logV) Zeit. Der Wert von E kann höchstens O(V2) sein, daher sind O(logV) und O(logE) gleich. Daher ist die Gesamtzeitkomplexität O(E * logE) oder O(E*logV) Hilfsraum: O(V + E), wobei V die Anzahl der Scheitelpunkte und E die Anzahl der Kanten im Diagramm ist. Dieser Artikel wurde von Aashish Barnwal zusammengestellt und vom techcodeview.com-Team überprüft.>