Een minimaal opspannende boom (MST) of minimum gewicht opspannende boom voor een gewogen, verbonden, ongerichte grafiek is een opspannende boom met een gewicht dat kleiner is dan of gelijk is aan het gewicht van elke andere opspannende boom. Voor meer informatie over de Minimum Spanning Tree raadpleegt u Dit artikel .
Inleiding tot het algoritme van Kruskal:
Hier zullen we bespreken Het algoritme van Kruskal om de MST van een gegeven gewogen grafiek te vinden.
Sorteer in het algoritme van Kruskal alle randen van de gegeven grafiek in oplopende volgorde. Vervolgens blijft het nieuwe randen en knooppunten in de MST toevoegen als de nieuw toegevoegde rand geen cyclus vormt. Het kiest eerst de minimaal verzwaarde rand en uiteindelijk de maximaal verzwaarde rand. We kunnen dus zeggen dat het bij elke stap een lokaal optimale keuze maakt om de optimale oplossing te vinden. Dit is dus een Hieronder staan de stappen voor het vinden van MST met behulp van het algoritme van Kruskal:
- Sorteer alle randen in niet-afnemende volgorde van hun gewicht.
- Kies de kleinste rand. Controleer of het een cyclus vormt met de tot nu toe gevormde spanningsboom. Als de cyclus niet wordt gevormd, neem dan deze rand mee. Gooi het anders weg.
- Herhaal stap #2 totdat er (V-1) randen in de spanning tree zijn.
Stap 2 maakt gebruik van de Union-Find-algoritme om cycli te detecteren.
Daarom raden we aan het volgende bericht als voorwaarde te lezen.
- Union-Find-algoritme | Set 1 (Cyclus detecteren in een grafiek)
- Union-Find-algoritme | Set 2 (Vereniging op rang en padcompressie)
Het algoritme van Kruskal om de minimale kostenomspannende boom te vinden, maakt gebruik van de hebzuchtige benadering. De Greedy Choice is om de kleinste gewichtsrand te kiezen die geen cyclus veroorzaakt in de tot nu toe gebouwde MST. Laten we het begrijpen met een voorbeeld:
Illustratie:
Hieronder ziet u de illustratie van de bovenstaande aanpak:
Invoergrafiek:
De grafiek bevat 9 hoekpunten en 14 randen. De minimaal gevormde spanningsboom zal dus (9 – 1) = 8 randen hebben.
Na sortering:
Gewicht Bron Bestemming 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 Kies nu alle randen één voor één uit de gesorteerde lijst met randen
Stap 1: Kies rand 7-6. Er wordt geen cyclus gevormd, neem deze op.
Voeg rand 7-6 toe in de MST
Stap 2: Kies rand 8-2. Er wordt geen cyclus gevormd, neem deze op.
Voeg rand 8-2 toe in de MST
Stap 3: Kies rand 6-5. Er wordt geen cyclus gevormd, neem deze op.
Voeg rand 6-5 toe in de MST
Stap 4: Kies rand 0-1. Er wordt geen cyclus gevormd, neem deze op.
Voeg rand 0-1 toe in de MST
Stap 5: Kies rand 2-5. Er wordt geen cyclus gevormd, neem deze op.
Voeg rand 2-5 toe in de MST
Stap 6: Kies rand 8-6. Omdat het opnemen van deze rand resulteert in de cyclus, gooit u deze weg. Kies rand 2-3: Er wordt geen cyclus gevormd, neem deze op.
Voeg rand 2-3 toe in de MST
Stap 7: Kies rand 7-8. Omdat het opnemen van deze rand resulteert in de cyclus, gooit u deze weg. Kies rand 0-7. Er wordt geen cyclus gevormd, neem deze op.
Voeg rand 0-7 toe in MST
Stap 8: Kies rand 1-2. Omdat het opnemen van deze rand resulteert in de cyclus, gooit u deze weg. Kies rand 3-4. Er wordt geen cyclus gevormd, neem deze op.
Voeg rand 3-4 toe in de MST
Opmerking: Omdat het aantal randen in de MST gelijk is aan (V – 1), stopt het algoritme hier
Hieronder vindt u de implementatie van de bovenstaande aanpak:
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]>rang[s2]) { ouder[s2] = s1; } anders { ouder[s2] = s1; rang[s1] += 1; } } } }; class Graph { vectorint>> edgelist; in TV; openbaar: Grafiek(int V) { this->V = V; } // Functie om rand toe te voegen aan een grafiek void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() {// Sorteer alle randen sort(edgelist.begin(), edgelist.end()); // Initialiseer de DSU DSU s(V); int ans = 0; uit<< '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
// 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]>rang[v]) { ouder[v] = u; } anders { ouder[v] = u; // Omdat de rang toeneemt als // de rangorde van twee sets dezelfde rang heeft[u]++; } } // Functie om de MST void kruskalAlgo(int n, int edge[n][3]) te vinden {/ // Eerst sorteren we de edge-array in oplopende volgorde // zodat we toegang hebben tot minimale afstanden/kosten qsort(edge , n, groottevan(rand[0]), vergelijker); int ouder[n]; int rang[n]; // Functie om parent[] en rank[] makeSet(parent, rank, n) te initialiseren; // Om de minimale kosten op te slaan int minCost = 0; printf( 'Hierna volgen de randen in de geconstrueerde MST
'); for (int i = 0; i int v1 = findParent(bovenliggende, rand[i][0]); int v2 = findParent(bovenliggende, rand[i][1]); int wt = rand[i][2] ; // Als de ouders verschillend zijn, betekent dat // dat ze zich in verschillende sets bevinden, dus // voeg ze samen if (v1 != v2) { unionSet(v1, v2, parent, rank, nCost += wt; '%d -- %d == %d
', edge[i][0], edge[i][1], wt } } printf('Minimale kostenomspannende structuur: %d n', minCost); // Stuurprogrammacode int main() { int edge[5][3] = { { 0, 1, 10 }, { 0, 2, 6 }, { 0, 3, 5 } , { 1, 3, 15 }, { 2, 3, 4 } }; kruskalAlgo(5, rand); |
>
// 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>>>Python3
Java-tekenreeks met formaat
# 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]>rang[y]: parent[y] = x # Als de rangen hetzelfde zijn, maak er dan één als root # en verhoog de rang met één anders: parent[y] = x rank[x] += 1 # De belangrijkste functie die moet worden geconstrueerd MST # gebruikt het algoritme van Kruskal def KruskalMST(self): # Dit slaat het resulterende MST-resultaat op = [] # Een indexvariabele, gebruikt voor gesorteerde randen i = 0 # Een indexvariabele, gebruikt voor resultaat [] e = 0 # Sorteer alle randen in # niet-afnemende volgorde van hun # gewicht self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] # Maak V-subsets met afzonderlijke elementen for node in range(self.V): parent.append(node) rank.append(0) # Aantal te nemen randen is kleiner dan tot V-1 terwijl e>>C#
// 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->Nee. aantal hoekpunten & E->aantal randen>>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; // Als de rangen hetzelfde zijn, maak er dan één aan als root // en verhoog de rang met nog één { subsets[yroot].parent = xroot; subsets[xroot].rank++; } } // De belangrijkste functie om MST te construeren // met behulp van Kruskal's algoritme void KruskalMST() {// Dit zal het // resulterende MST Edge[] resultaat = new Edge[V] opslaan; // Een indexvariabele, gebruikt voor result[] int e = 0; // Een indexvariabele, gebruikt voor gesorteerde randen int i = 0; for (i = 0; i result[i] = new Edge(); // Sorteer alle randen in niet-afnemende // volgorde van hun gewicht. Als we // de gegeven grafiek niet mogen wijzigen, kunnen we // een kopie van de reeks randen Array.Sort(edge); // Wijs geheugen toe voor het maken van V-subsets subset[] subsets = nieuwe subset[V]; ; // Maak V-subsets met enkele elementen voor (int v = 0; v subsets[v].parent = v; subsets[v].rank = 0; } i = 0; // Aantal te nemen randen is gelijk naar V-1 while (e // Kies de kleinste rand. En verhoog // de index voor de volgende iteratie Edge next_edge = new Edge(); next_edge = edge[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest); // Als het opnemen van deze rand geen cyclus veroorzaakt, // neem het dan op in het resultaat en verhoog de index // van het resultaat voor de volgende rand if (x != y) { result[e++] = next_edge; Union(subsets, x, y); } // Druk de inhoud van result[] af om // de ingebouwde MST Console.WriteLine('Hierna volgen de randen in ' + ' de gebouwde MST'); int minimumkosten = 0; for (i = 0; i Console.WriteLine(resultaat[i].src + ' -- ' + resultaat[i].dest + ' == ' + resultaat[i].gewicht); minimumCost += result[i].weight; } Console.WriteLine('Minimumkosten overspannende structuur: ' + minimumCost Console.ReadLine(); } // Bestuurderscode public static void Main(String[] args) { int V = 4; int E = 5; Grafiekgrafiek = nieuwe grafiek (V, E); // voeg rand 0-1 toe grafiek.edge[0].src = 0; graph.edge[0].weight = 10; // voeg rand 0-2 toe graph.edge[1].src = 0; graph.edge[1].dest = 2 ; // voeg rand 0-3 toe grafiek.edge[2].src = 0; grafiek.edge[2].dest = 3; grafiek.edge[2].weight = 5 // voeg rand 1-3 grafiek toe. edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 15; // voeg edge 2-3 toe graph.edge[4].src = 2; .edge[4].dest = 3; graph.edge[4].weight = 4; // Functieaanroep graph.KruskalMST(); } } // Deze code is bijgedragen door Aakash Hasija>>>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)=>{ retourneer a[2] - b[2]; }) // ingebouwde snelle sorteerfunctie wordt geleverd met stdlib.h // ga naar https://www.techcodeview.com Het sorteren van randen kost O(E * logE) tijd. Na het sorteren doorlopen we alle randen en passen we het find-union-algoritme toe. De zoek- en samenvoegingsbewerkingen kunnen maximaal O(logV) tijd in beslag nemen. De algehele complexiteit is dus O(E * logE + E * logV) tijd. De waarde van E kan maximaal O(V2) zijn, dus O(logV) en O(logE) zijn hetzelfde. Daarom is de algehele tijdscomplexiteit O(E * logE) of O(E*logV). Hulpruimte: O(V + E), waarbij V het aantal hoekpunten is en E het aantal randen in de grafiek. Dit artikel is samengesteld door Aashish Barnwal en beoordeeld door het techcodeview.com-team.>