Et minimum spændingstræ (MST) eller minimumvægtspændingstræ for en vægtet, forbundet, urettet graf er et spændingstræ med en vægt, der er mindre end eller lig med vægten af hvert andet spændingstræ. For at lære mere om Minimum Spanning Tree, se denne artikel .
Introduktion til Kruskals algoritme:
Her vil vi diskutere Kruskals algoritme at finde MST for en given vægtet graf.
I Kruskals algoritme skal du sortere alle kanter af den givne graf i stigende rækkefølge. Så bliver den ved med at tilføje nye kanter og noder i MST, hvis den nyligt tilføjede kant ikke danner en cyklus. Den vælger den mindste vægtede kant først og den maksimalt vægtede kant til sidst. Således kan vi sige, at den træffer et lokalt optimalt valg i hvert trin for at finde den optimale løsning. Derfor er dette en Nedenfor er trinene til at finde MST ved hjælp af Kruskals algoritme:
- Sorter alle kanter i ikke-faldende rækkefølge efter deres vægt.
- Vælg den mindste kant. Tjek, om det danner en cyklus med det spændingstræ, der er dannet indtil videre. Hvis cyklussen ikke er dannet, inkluderes denne kant. Ellers, kasser det.
- Gentag trin #2, indtil der er (V-1) kanter i spændingstræet.
Trin 2 bruger Union-Find algoritme at detektere cyklusser.
Så vi anbefaler at læse følgende indlæg som en forudsætning.
- Union-Find Algoritme | Sæt 1 (Detekter cyklus i en graf)
- Union-Find Algoritme | Sæt 2 (sammenslutning efter rang- og stikomprimering)
Kruskals algoritme til at finde minimumsomkostningsspændingstræet bruger den grådige tilgang. Det grådige valg er at vælge den mindste vægtkant, der ikke forårsager en cyklus i den hidtil konstruerede MST. Lad os forstå det med et eksempel:
Illustration:
Nedenfor er illustrationen af ovenstående fremgangsmåde:
binært søgetræ
Input graf:
Grafen indeholder 9 hjørner og 14 kanter. Så det dannede minimumspændende træ vil have (9 – 1) = 8 kanter.
Efter sortering:
Vægt Kilde Bestemmelsessted 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 elleve 1 7 14 3 5 Vælg nu alle kanter én efter én fra den sorterede liste over kanter
Trin 1: Pluk kant 7-6. Der dannes ingen cyklus, medtag den.
Tilføj kant 7-6 i MST
Trin 2: Pluk kant 8-2. Der dannes ingen cyklus, medtag den.
Tilføj kant 8-2 i MST
Trin 3: Pluk kant 6-5. Der dannes ingen cyklus, medtag den.
Tilføj kant 6-5 i MST
Trin 4: Vælg kant 0-1. Der dannes ingen cyklus, medtag den.
Tilføj kant 0-1 i MST
Trin 5: Pluk kant 2-5. Der dannes ingen cyklus, medtag den.
Tilføj kant 2-5 i MST
Trin 6: Pluk kant 8-6. Da at inkludere denne kant resulterer i cyklussen, skal du kassere den. Vælg kant 2-3: Der dannes ingen cyklus, medtag den.
Tilføj kant 2-3 i MST
Trin 7: Pluk kant 7-8. Da at inkludere denne kant resulterer i cyklussen, skal du kassere den. Vælg kant 0-7. Der dannes ingen cyklus, medtag den.
Tilføj kant 0-7 i MST
Trin 8: Pluk kant 1-2. Da at inkludere denne kant resulterer i cyklussen, skal du kassere den. Pluk kant 3-4. Der dannes ingen cyklus, medtag den.
Tilføj kant 3-4 i MST
Bemærk: Da antallet af kanter inkluderet i MST er lig med (V – 1), så stopper algoritmen her
Nedenfor er implementeringen af ovenstående tilgang:
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]) { forælder[s2] = s1; } andet { forælder[s2] = s1; rang[s1] += 1; } } } }; klasse Graph { vectorint>> edgelist; int V; public: Graph(int V) { this->V = V; } // Funktion til at tilføje kant i en graf void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() { // Sort all edges sort(edgelist.begin(), edgelist.end()); // Initialiser 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
linux kommandoer
// 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]) { forælder[v] = u; } andet { forælder[v] = u; // Da rangen stiger, hvis // rækkerne af to sæt er samme rang[u]++; } } // Funktion til at finde MST void kruskalAlgo(int n, int edge[n][3]) { // Først sorterer vi kant-arrayet i stigende rækkefølge //, så vi kan få adgang til minimum distances/cost qsort(edge , n, sizeof(edge[0]), komparator); int forælder[n]; int rang[n]; // Funktion til at initialisere parent[] og rank[] makeSet(parent, rank, n); // For at gemme de minimale omkostninger int minCost = 0; printf( 'Følgende er kanterne i den konstruerede MST
'); for (int i = 0; i int v1 = findParent(forælder, kant[i][0]); int v2 = findParent(forælder, kant[i][1]); int wt = kant[i][2] ; // Hvis forældrene er forskellige, betyder det, at de er i forskellige sæt, så // union dem if (v1 != v2) { unionSet(v1, minCost, n); '%d -- %d == %d
', edge[i][0], edge[i][1], wt } } printf('Minimumsomkostningstræ: %d); n', minCost); } // Driverkode int main() { int edge[5][3] = { { 0, 1, 10 }, { 0, 2, 6 }, { 0, 3, 5 } , { 1, 3, 15 }, { 2, 3, 4 } } kruskalAlgo(5, kant }>'>; |
>
// 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>hvordan man sorterer et array i java>>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]: forælder[y] = x # Hvis rækkerne er ens, lav en som root # og øg dens rang med en anden: forælder[y] = x rang[x] += 1 # Hovedfunktionen til at konstruere MST # ved hjælp af Kruskal's algoritme def KruskalMST(selv): # Dette vil gemme det resulterende MST-resultat = [] # En indeksvariabel, der bruges til sorterede kanter i = 0 # En indeksvariabel, der bruges til resultat[] e = 0 # Sorter alle kanter i # ikke-aftagende rækkefølge efter deres # vægt self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] # Opret V undersæt med enkelte elementer for node in range(self.V): parent.append(node) rank.append(0) # Antal kanter, der skal tages, er mindre end til V-1, mens 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->ingen. af hjørner & 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>subsets[yroot].rang) subsets[yroot].parent = xroot; // Hvis rækkerne er de samme, lav en som root // og øg dens rang med en anden { subsets[yroot].parent = xroot; undersæt[xroot].rang++; } } // Hovedfunktionen til at konstruere MST // ved hjælp af Kruskal's algoritme void KruskalMST() { // Dette vil gemme // resulterende MST Edge[] resultat = new Edge[V]; // En indeksvariabel, der bruges til resultat[] int e = 0; // En indeksvariabel, der bruges til sorterede kanter int i = 0; for (i = 0; i result[i] = new Edge(); // Sorter alle kanter i ikke-aftagende // rækkefølge efter deres vægt. Hvis vi ikke har lov til // at ændre den givne graf, kan vi oprette // en kopi af array af kanter Array.Sort(edge) // Tildel hukommelse til at skabe V undersæt[] undersæt = ny undermængde[V]; ; // Opret V undersæt med enkelte elementer for (int v = 0; v undersæt[v].parent = v; undersæt[v].rang = 0; } i = 0; // Antal kanter, der skal tages, er lig til V-1 while (e // Vælg den mindste kant. Og forøg // indekset for næste iteration Edge next_edge = new Edge(); next_edge = edge[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest); // Hvis inkluderende denne kant ikke forårsager cyklus, // inkludere den i resultatet og inkrementere indekset // af resultatet for næste kant hvis (x != y) { result[e++] = next_edge(undersæt, x, y } } // Udskriv indholdet af resultat[] for at vise // den indbyggede MST Console.WriteLine('Følgende er kanterne i ' + '); den konstruerede MST'); int minimumCost = 0; for (i = 0; i Console.WriteLine(result[i].src + ' -- ' + resultat[i].dest + ' == ' + resultat[i].vægt); minimumCost += 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; 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(} } // Denne kode er bidraget af Aakash Hasija>>>Javascript
hvad er const i java
>// 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)=>{ returner a[2] - b[2]; }) //indbygget hurtigsorteringsfunktion leveres med stdlib.h //gå til https://www.techcodeview.com Sortering af kanter tager O(E * logE) tid. Efter sortering itererer vi gennem alle kanter og anvender find-union-algoritmen. Find- og fagforeningsoperationerne kan højst tage O(logV) tid. Så overordnet kompleksitet er O(E * logE + E * logV) tid. Værdien af E kan højst være O(V2), så O(logV) og O(logE) er de samme. Derfor er den overordnede tidskompleksitet O(E * logE) eller O(E*logV) Auxiliary Space: O(V + E), hvor V er antallet af hjørner og E er antallet af kanter i grafen. Denne artikel er udarbejdet af Aashish Barnwal og gennemgået af techcodeview.com-teamet.>