Ett minsta spännträd (MST) eller minimumviktspännande träd för en viktad, sammankopplad, oriktad graf är ett spännträd med en vikt som är mindre än eller lika med vikten av vartannat spännträd. För att lära dig mer om Minimum Spanning Tree, se Denna artikel .
Introduktion till Kruskals algoritm:
Här ska vi diskutera Kruskals algoritm för att hitta MST för en given viktad graf.
I Kruskals algoritm, sortera alla kanter på den givna grafen i ökande ordning. Sedan fortsätter den att lägga till nya kanter och noder i MST om den nyligen tillagda kanten inte bildar en cykel. Den väljer den minsta viktade kanten först och den maximalt viktade kanten till sist. Därmed kan vi säga att den gör ett lokalt optimalt val i varje steg för att hitta den optimala lösningen. Därför är detta en Nedan följer stegen för att hitta MST med Kruskals algoritm:
- Sortera alla kanter i icke-minskande ordning efter vikt.
- Välj den minsta kanten. Kontrollera om det bildar en cykel med spännträdet som har bildats hittills. Om cykeln inte bildas, inkludera denna kant. Annars, släng det.
- Upprepa steg #2 tills det finns (V-1) kanter i spännträdet.
Steg 2 använder Union-Find-algoritm för att upptäcka cykler.
Så vi rekommenderar att du läser följande inlägg som en förutsättning.
- Union-Find Algoritm | Set 1 (Detektera cykel i en graf)
- Union-Find Algoritm | Set 2 (Union By Rank and Path Compression)
Kruskals algoritm för att hitta lägsta kostnadsöverskridande träd använder den giriga metoden. Det giriga valet är att välja den minsta viktkanten som inte orsakar en cykel i den hittills konstruerade MST. Låt oss förstå det med ett exempel:
Illustration:
Nedan är illustrationen av ovanstående tillvägagångssätt:
Inmatningsdiagram:
Grafen innehåller 9 hörn och 14 kanter. Så det minsta spännträd som bildas kommer att ha (9 – 1) = 8 kanter.
Efter sortering:
Vikt Källa Destination 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 elva 1 7 14 3 5 Välj nu alla kanter en efter en från den sorterade listan med kanter
Steg 1: Plockkant 7-6. Ingen cykel bildas, inkludera den.
Lägg till kant 7-6 i MST
Steg 2: Välj kant 8-2. Ingen cykel bildas, inkludera den.
Lägg till kant 8-2 i MST
Steg 3: Plockkant 6-5. Ingen cykel bildas, inkludera den.
Lägg till kant 6-5 i MST
Steg 4: Välj kant 0-1. Ingen cykel bildas, inkludera den.
Lägg till kant 0-1 i MST
Steg 5: Plockkant 2-5. Ingen cykel bildas, inkludera den.
Lägg till kant 2-5 i MST
Steg 6: Plockkant 8-6. Eftersom inkludering av denna kant resulterar i cykeln, kassera den. Välj kant 2-3: Ingen cykel bildas, inkludera den.
Lägg till kant 2-3 i MST
Steg 7: Plockkant 7-8. Eftersom inkludering av denna kant resulterar i cykeln, kassera den. Välj kant 0-7. Ingen cykel bildas, inkludera den.
Lägg till kant 0-7 i MST
Steg 8: Välj kant 1-2. Eftersom inkludering av denna kant resulterar i cykeln, kassera den. Välj kant 3-4. Ingen cykel bildas, inkludera den.
Lägg till kant 3-4 i MST
Notera: Eftersom antalet kanter som ingår i MST är lika med (V – 1), så stannar algoritmen här
Nedan är implementeringen av ovanstående tillvägagångssätt:
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]) { förälder[s2] = s1; } annat { förälder[s2] = s1; rang[s1] += 1; } } } }; class Graph { vectorint>> edgelist; på tv; public: Graph(int V) { this->V = V; } // Funktion för att lägga till kant i en graf void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() { // Sortera alla kanter sort(edgelist.begin(), edgelist.end()); // Initiera 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]>rang[v]) { förälder[v] = u; } annat { förälder[v] = u; // Eftersom rangen ökar om // rangorden för två uppsättningar är samma rang[u]++; } } // Funktion för att hitta MST void kruskalAlgo(int n, int edge[n][3]) { // Först sorterar vi kantmatrisen i stigande ordning // så att vi kan komma åt minimiavstånd/kostnad qsort(edge , n, sizeof(edge[0]), komparator); int förälder[n]; int rang[n]; // Funktion för att initiera förälder[] och rang[] makeSet(förälder, rang, n); // För att lagra minimikostnaden int minCost = 0; printf( 'Följande är kanterna i den konstruerade MST
'); för (int i = 0; i int v1 = findParent(förälder, kant[i][0]); int v2 = findParent(förälder, kant[i][1]); int wt = kant[i][2] ; // Om föräldrarna är olika att // betyder att de är i olika uppsättningar så // union dem if (v1 != v2) { unionSet(v1, minCost, n; '%d -- %d == %d
', edge[i][0], edge[i][1], wt } } printf('Minimumkostnadsträd: %d); n', minCost); } // Drivrutinskod int main() { int edge[5][3] = { { 0, 1, 10 }, { 0, 2, 6 }, { 0, 3, 5 } , { 1, 3, 15 }, { 2, 3, 4 } } kruskalAlgo(5, edge }>'>; |
>
// 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]>rang[y]: förälder[y] = x # Om rangorden är samma, gör sedan en som rot # och öka dess rang med en annan: förälder[y] = x rang[x] += 1 # Huvudfunktionen att konstruera MST # använder Kruskals algoritm def KruskalMST(själv): # Detta kommer att lagra det resulterande MST-resultatet = [] # En indexvariabel som används för sorterade kanter i = 0 # En indexvariabel som används för resultat[] e = 0 # Sortera alla kanter i # icke-minskande ordning efter deras # vikt self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] # Skapa V-delmängder med enstaka element för nod i intervallet(self.V): parent.append(nod) rank.append(0) # Antal kanter som ska tas är mindre än till V-1 medan 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->Nej. av hörn & E->antal kanter>>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>subset[yroot].rank) subset[yroot].parent = xroot; // Om rangorden är samma, gör sedan en som root // och öka dess rang med en annan { subset[yroot].parent = xroot; delmängder[xroot].rank++; } } // Huvudfunktionen för att konstruera MST // med Kruskal's algoritm void KruskalMST() { // Detta kommer att lagra // resulterande MST Edge[]-resultat = new Edge[V]; // En indexvariabel som används för resultat[] int e = 0; // En indexvariabel som används för sorterade kanter int i = 0; för (i = 0; i resultat[i] = new Edge(); // Sortera alla kanter i icke-minskande // ordning efter deras vikt. Om vi inte tillåts // att ändra den givna grafen kan vi skapa // en kopia av array of edges Array.Sort(edge) // Tilldela minne för att skapa V delmängder[] delmängder = ny delmängd[V]; ; // Skapa V delmängder med enstaka element för (int v = 0; v delmängder[v].parent = v; delmängder[v].rank = 0; } i = 0; // Antal kanter som ska tas är lika till V-1 while (e // Välj den minsta kanten. Och öka // indexet för nästa iteration Edge next_edge = new Edge(); next_edge = edge[i++]; int x = find(subsets, next_edge.src); int y = find(subset, next_edge.dest); // Om inkludering av denna kant inte orsakar cykel, // inkludera den i resultatet och öka indexet // av resultatet för nästa kant om (x != y) { result[e++] = next_edge (underuppsättningar, x, y } } // Skriv ut innehållet i resultatet[] för att visa // den inbyggda MST Console.WriteLine('Följande är kanterna i ' + '); den konstruerade MST'); int minimumCost = 0; för (i = 0; i Console.WriteLine(result[i].src + ' -- ' + resultat[i].dest + ' == ' + resultat[i].vikt); minimumKostnad += result[i].weight; } Console.WriteLine('Minimum Cost Spanning Tree: ' + minimumCost Console.ReadLine(} // Driver's Code public static void Main(String[] args); int V = 4; int E = 5; Graph graph = new Graph(V, E). graph.edge[0].weight = 10; // add edge 0-2 graph.edge[1].src = 0; graph.edge[1].dest = 2; ; // add edge 0-3 graph.edge[2].src = 0; graph.edge[2].dest = 3.weight = 5; edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 15; // add edge 2-3 graph.edge[4] .edge[4].dest = 3; graph.edge[4].weight = 4; // Function call graph.KruskalMST(} } // Denna kod är bidragit från Aakash Hasija>>>Javascript
hur man hittar blockerade nummer på Android
>// 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)=>{ returnera a[2] - b[2]; }) //inbyggd snabbsorteringsfunktion kommer med stdlib.h //gå till https://www.techcodeview.com Sortering av kanter tar O(E * logE) tid. Efter sortering itererar vi genom alla kanter och tillämpar algoritmen för hitta-union. Hitta och fackliga operationer kan ta högst O(logV) tid. Så övergripande komplexitet är O(E * logE + E * logV) tid. Värdet på E kan som mest vara O(V2), så O(logV) och O(logE) är samma. Därför är den totala tidskomplexiteten O(E * logE) eller O(E*logV) Hjälprum: O(V + E), där V är antalet hörn och E är antalet kanter i grafen. Den här artikeln är sammanställd av Aashish Barnwal och granskad av techcodeview.com-teamet.>