Kruskalov algoritmus minimálneho spanningového stromu (MST).
Minimálny kostra (MST) alebo kostra s minimálnou váhou pre vážený, spojený, neusmernený graf je kostra s hmotnosťou menšou alebo rovnou váhe každej inej kostry. Ak sa chcete dozvedieť viac o minimálnom spanningovom strome, pozrite si tento článok .
Úvod do Kruskalovho algoritmu:
Tu budeme diskutovať Kruskalov algoritmus nájsť MST daného váženého grafu.
V Kruskalovom algoritme zoraďte všetky hrany daného grafu v rastúcom poradí. Potom pokračuje v pridávaní nových hrán a uzlov v MST, ak novo pridaná hrana netvorí cyklus. Najprv vyberie minimálnu váženú hranu a nakoniec maximálnu váženú hranu. Môžeme teda povedať, že v každom kroku robí lokálne optimálny výber s cieľom nájsť optimálne riešenie. Toto je teda a Nižšie sú uvedené kroky na nájdenie MST pomocou Kruskalovho algoritmu:
- Zoraďte všetky hrany v neklesajúcom poradí podľa ich hmotnosti.
- Vyberte najmenšiu hranu. Skontrolujte, či tvorí cyklus s doteraz vytvoreným kostrou. Ak sa cyklus nevytvorí, zahrňte túto hranu. V opačnom prípade to zahoďte.
- Opakujte krok č. 2, kým nebudú v kostre (V-1) hrany.
Krok 2 používa Algoritmus Union-Find na detekciu cyklov.
Preto odporúčame prečítať si nasledujúci príspevok ako predpoklad.
- Algoritmus Union-Find | Sada 1 (detekcia cyklu v grafe)
- Algoritmus Union-Find | Sada 2 (Spojenie podľa hodnotenia a kompresie cesty)
Kruskalov algoritmus na nájdenie stromu minimálnych nákladov používa chamtivý prístup. Greedy Choice je vybrať najmenšiu hranu hmotnosti, ktorá nespôsobuje cyklus v doteraz skonštruovanom MST. Poďme to pochopiť na príklade:
Ilustrácia:
Nižšie je ilustrácia vyššie uvedeného prístupu:
Vstupný graf:
Graf obsahuje 9 vrcholov a 14 hrán. Takže minimálny vytvorený kostra bude mať (9 – 1) = 8 hrán.
Po zoradení:
Hmotnosť Zdroj Destinácia 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 jedenásť 1 7 14 3 5 Teraz postupne vyberte všetky hrany zo zoradeného zoznamu hrán
Krok 1: Vyberte okraj 7-6. Netvorí sa žiadny cyklus, zahrňte ho.
Pridajte hranu 7-6 v MST
Krok 2: Vyberte okraj 8-2. Netvorí sa žiadny cyklus, zahrňte ho.
Pridajte hranu 8-2 v MST
Krok 3: Vyberte okraj 6-5. Netvorí sa žiadny cyklus, zahrňte ho.
Pridajte hranu 6-5 v MST
Krok 4: Vyberte hranu 0-1. Netvorí sa žiadny cyklus, zahrňte ho.
Pridajte hranu 0-1 v MST
Krok 5: Vyberte okraj 2-5. Netvorí sa žiadny cyklus, zahrňte ho.
Pridajte hranu 2-5 v MST
Krok 6: Vyberte okraj 8-6. Keďže zahrnutie tejto hrany má za následok cyklus, zahoďte ju. Vyberte okraj 2-3: Netvorí sa žiadny cyklus, zahrňte ho.
Pridajte hranu 2-3 v MST
Krok 7: Vyberte okraj 7-8. Keďže zahrnutie tejto hrany má za následok cyklus, zahoďte ju. Vyberte okraj 0-7. Netvorí sa žiadny cyklus, zahrňte ho.
Pridajte hranu 0-7 v MST
Krok 8: Vyberte okraj 1-2. Keďže zahrnutie tejto hrany má za následok cyklus, zahoďte ju. Vyberte okraj 3-4. Netvorí sa žiadny cyklus, zahrňte ho.
Pridajte hranu 3-4 v MST
Poznámka: Keďže počet hrán zahrnutých v MST sa rovná (V – 1), algoritmus sa tu zastaví
Nižšie je uvedená implementácia vyššie uvedeného prístupu:
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]>poradie[s2]) { rodič[s2] = s1; } else { rodič[s2] = s1; poradie[s1] += 1; } } } }; class Graph { vectorint>> edgelist; int V; public: Graph(int V) { this->V = V; } // Funkcia na pridanie hrany do grafu void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() { // Zoradiť všetky hrany sort(edgelist.begin(), edgelist.end()); // Inicializácia 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
// 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]>poradie[v]) { rodič[v] = u; } else { rodič[v] = u; // Keďže sa hodnosť zvyšuje, ak // hodnosti dvoch množín majú rovnakú hodnosť[u]++; } } // Funkcia na nájdenie MST void kruskalAlgo(int n, int hrana[n][3]) { // Najprv zoradíme pole okrajov vo vzostupnom poradí //, aby sme mali prístup k minimálnym vzdialenostiam/nákladom qsort(edge , n, sizeof(edge[0]), komparátor); int parent[n]; int rank[n]; // Funkcia na inicializáciu rodiča[] a poradia[] makeSet(parent, rank, n); // Uloženie minimálnych nákladov int minCost = 0; printf( 'Nasledujú okraje v skonštruovanom MST
'); for (int i = 0; i int v1 = nájsť rodiča(rodič, hrana[i][0]); int v2 = nájsť rodiča(rodič, hrana[i][1]); int wt = hrana[i][2] ; // Ak sú rodičia rozdielni, // znamená, že sú v rôznych množinách, takže // zjednoťte ich if (v1 != v2) { minCost += wt; '%d -- %d == %d
', hrana[i][0], hrana[i][1], wt } } printf('Strom minimálnych nákladov: %d); n', minCost } // Kód ovládača int main() { int okraj[5][3] = { { 0, 1, 10 }, { 0, 2, 6 }, { 0, 3, 5 } , {1, 3, 15 }, { 2, 3, 4 } }; kruskalAlgo(5, hrana 0; |
>
// 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
# 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]>poradie[y]: rodič[y] = x # Ak sú poradia rovnaké, urobte jeden ako koreň # a zvýšte jeho poradie o jedno ďalšie: rodič[y] = x poradie[x] += 1 # Hlavná funkcia, ktorú treba zostrojiť MST # pomocou Kruskalovho algoritmu def KruskalMST(self): # Toto uloží výsledný výsledok MST = [] # Indexová premenná, použitá pre zoradené hrany i = 0 # Indexová premenná, použitá pre výsledok[] e = 0 # Zoraďte všetky hrany v # neklesajúcom poradí podľa # ich hmotnosti self.graph = zoradené (self.graph, key=lambda item: item[2]) parent = [] rank = [] # Vytvorte V podmnožiny s jednotlivými prvkami for node in range(self.V): parent.append(node) rank.append(0) # Počet hrán, ktoré sa majú vziať, je menší ako V-1, zatiaľ čo 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->č. vrcholov & E->počet hrán>>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; // Ak sú hodnosti rovnaké, potom urobte jednu ako root // a zvýšte jej hodnosť o jednu else { subsets[yroot].parent = xroot; podmnožiny[xroot].rank++; } } // Hlavná funkcia na zostavenie MST // pomocou Kruskalovho algoritmu void KruskalMST() { // Toto uloží // výsledný výsledok MST Edge[] = new Edge[V]; // Indexová premenná, použitá pre výsledok[] int e = 0; // Indexová premenná, používaná pre zoradené hrany int i = 0; for (i = 0; i result[i] = new Edge(); // Zoradiť všetky hrany v neklesajúcom // poradí ich hmotnosti. Ak nám nie je dovolené // daný graf zmeniť, môžeme vytvoriť // kópia poľa hrán Array.Sort(edge) // Alokácia pamäte na vytvorenie V podmnožín subset[] subsets = new subset[V] for (i = 0; i subsets[i] = new subset(); ; // Vytvorenie podmnožín V s jednotlivými prvkami pre (int v = 0; v podmnožiny[v].rodič = v; podmnožiny[v].rank = 0; } i = 0; // Počet hrán, ktoré sa majú vziať, je rovnaký na V-1 while (e // Vyberte najmenšiu hranu. A zvýšte // index pre ďalšiu iteráciu Edge next_edge = new Edge(); next_edge = edge[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest) // Ak zahrnutie tejto hrany nespôsobí cyklus, // zahrnie ju do výsledku a zvýši index // výsledku pre ďalšiu hranu if (x != y) {); vysledok[e++] = dalsia_hrana (subsets, x, y } // Vypis obsahu vysledku[] na zobrazenie // zostavenej konzoly MST.WriteLine('Nasleduje hrany v ' + '); vytvorený MST'); int minimalne naklady = 0; for (i = 0; i Console.WriteLine(vysledok[i].src + ' -- ' + vysledok[i].ciel + ' == ' + vysledok[i].hmotnost); minimalneCena += vysledok[i].hmotnost } Console.WriteLine('Strom minima nakladov: ' + minimumCost Console.ReadLine( } // Kód vodiča public static void Main(String[] args)); int V = 4; int E = 5; Graf graf = new Graf(V, E); graf.hrana[0].váha = 10; // pridanie hrany 0-2 graf.hrana[1].src = 0; ; // pridaj hranu 0-3 graf.hrana[2].src = 0; hrana[3].src = 1; graf.hrana[3].dest = 3; .edge[4].dest = 3; graph.edge[4].weight = 4; // Volanie funkcie graph.KruskalMST( } } // Tento kód prispel Aakash Hasija>'>;
>
>// 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]; }) //vstavaná funkcia rýchleho triedenia je súčasťou stdlib.h //prejdite na https://www.techcodeview.com Triedenie hrán trvá O(E * logE) čas. Po zoradení iterujeme cez všetky hrany a aplikujeme algoritmus find-union. Operácie vyhľadávania a spojenia môžu trvať najviac O(logV) času. Celková zložitosť je teda čas O(E * logE + E * logV). Hodnota E môže byť najviac O(V2), takže O(logV) a O(logE) sú rovnaké. Preto je celková časová zložitosť O(E * logE) alebo O(E*logV) Pomocný priestor: O(V + E), kde V je počet vrcholov a E je počet hrán v grafe. Tento článok zostavil Aashish Barnwal a preskúmal ho tím techcodeview.com.>
