Vähintään ulottuva puu (MST) tai painotetun, yhdistetyn, suuntaamattoman graafin vähimmäispainoinen virittävä puu on virittävä puu, jonka paino on pienempi tai yhtä suuri kuin jokaisen muun virittävän puun paino. Saat lisätietoja Minimum Spanning Tree -puusta osoitteesta Tämä artikkeli .
Johdatus Kruskalin algoritmiin:
Täällä keskustellaan Kruskalin algoritmi löytääksesi tietyn painotetun kaavion MST:n.
Lajittele Kruskalin algoritmissa annetun graafin kaikki reunat kasvavaan järjestykseen. Sitten se jatkaa uusien reunojen ja solmujen lisäämistä MST:hen, jos vasta lisätty reuna ei muodosta sykliä. Se valitsee ensin pienimmän painotetun reunan ja lopuksi suurimman painotetun reunan. Näin ollen voidaan sanoa, että se tekee jokaisessa vaiheessa paikallisesti optimaalisen valinnan optimaalisen ratkaisun löytämiseksi. Siksi tämä on a Alla on vaiheet MST:n löytämiseksi Kruskalin algoritmilla:
- Lajittele kaikki reunat painonsa mukaan ei-laskevaan järjestykseen.
- Valitse pienin reuna. Tarkista, muodostaako se syklin tähän mennessä muodostetun virittävän puun kanssa. Jos sykliä ei muodosteta, sisällytä tämä reuna. Muuten hävitä se.
- Toista vaihe 2, kunnes virittävässä puussa on (V-1) reunat.
Vaihe 2 käyttää Union-Find-algoritmi syklien havaitsemiseksi.
Joten suosittelemme seuraavan postauksen lukemista edellytyksenä.
- Union-Find-algoritmi | Sarja 1 (Havaitse sykli kaaviossa)
- Union-Find-algoritmi | Sarja 2 (liitto sijoituksen ja polun pakkauksen mukaan)
Kruskalin algoritmi vähimmäiskustannusten kattavan puun löytämiseksi käyttää ahneutta. Greedy Choice on valita pienin painoreuna, joka ei aiheuta sykliä tähän mennessä rakennetussa MST:ssä. Ymmärrämme sen esimerkin avulla:
Kuva:
Alla on esimerkki yllä olevasta lähestymistavasta:
Syöttökaavio:
Graafi sisältää 9 kärkeä ja 14 reunaa. Muodostetulla vähimmäisvirittävällä puulla on siis (9 – 1) = 8 reunaa.
Lajittelun jälkeen:
Paino Lähde Kohde 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 yksitoista 1 7 14 3 5 Valitse nyt kaikki reunat yksitellen järjestetystä reunaluettelosta
Vaihe 1: Poimintareuna 7-6. Kiertoa ei muodostu, ota se mukaan.
Lisää reuna 7-6 MST:hen
Vaihe 2: Poimintareuna 8-2. Kiertoa ei muodostu, ota se mukaan.
Lisää reuna 8-2 MST:hen
Vaihe 3: Poimintareuna 6-5. Kiertoa ei muodostu, ota se mukaan.
Lisää reuna 6-5 MST:hen
Vaihe 4: Valintaerä 0-1. Kiertoa ei muodostu, ota se mukaan.
Lisää reuna 0-1 MST:ssä
Vaihe 5: Poimintareuna 2-5. Kiertoa ei muodostu, ota se mukaan.
Lisää reuna 2-5 MST:hen
Vaihe 6: Poimintareuna 8-6. Koska tämän reunan sisällyttäminen johtaa sykliin, hylkää se. Valitse reuna 2-3: Kiertoa ei muodostu, ota se mukaan.
Lisää reuna 2-3 MST:hen
Vaihe 7: Poimintareuna 7-8. Koska tämän reunan sisällyttäminen johtaa sykliin, hylkää se. Valintareuna 0-7. Kiertoa ei muodostu, ota se mukaan.
vertailukelpoinen listaLisää reuna 0-7 MST:hen
Vaihe 8: Valitse reuna 1-2. Koska tämän reunan sisällyttäminen johtaa sykliin, hylkää se. Valitse reuna 3-4. Kiertoa ei muodostu, ota se mukaan.
Lisää reunat 3-4 MST:hen
Huomautus: Koska MST:n sisältämien reunojen määrä on (V – 1), algoritmi pysähtyy tähän
Alla on yllä olevan lähestymistavan toteutus:
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]) { vanhempi[s2] = s1; } else { vanhempi[s2] = s1; sijoitus[s1] += 1; } } } }; class Graph { vectorint>> reunalista; int V; public: Graph(int V) { this->V = V; } // Funktio reunan lisäämiseksi graafiin void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() { // Lajittele kaikki reunat sort(edgelist.begin(), edgelist.end()); // Alustaa 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]>sijoitus[v]) { vanhempi[v] = u; } else { vanhempi[v] = u; // Koska arvo kasvaa, jos // kahden joukon arvot ovat samat [u]++; } } // MST void:n etsimistoiminto kruskalAlgo(int n, int reuna[n][3]) { // Ensin lajitellaan reunataulukko nousevaan järjestykseen // jotta voimme tarkastella minimietäisyyksiä/kustannuksia qsort(edge , n, koko(reuna[0]), vertailija); int parent[n]; int rank[n]; // Funktio, jolla alustetaan vanhempi[] ja rank[] makeSet(parent, rank, n); // Vähimmäiskustannusten tallentaminen int minCost = 0; printf( 'Seuraavat rakennetun MST:n reunat
'); for (int i = 0; i int v1 = etsintäylä(emo, reuna[i][0]); int v2 = etsintäyläosa(kanta, reuna[i][1]); int wt = reuna[i][2] // Jos vanhemmat ovat erilaisia, // ne ovat eri joukoissa, joten // yhdistävät ne if (v1, v2, vanhempi, rank, n); '%d -- %d == %d
', edge[i][0], edge[i][1], wt } } printf('Minimikustannusten ulottuva puu: %d); n', minCost); , { 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>>>Python 3
# 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]: vanhempi[y] = x # Jos arvot ovat samat, tee yksi juuriksi # ja lisää sen arvoa yhdellä muulla: vanhempi[y] = x rank[x] += 1 # Rakentamisen pääfunktio MST # käyttäen Kruskalin algoritmia def KruskalMST(itse): # Tämä tallentaa tuloksena olevan MST-tuloksen = [] # Indeksimuuttuja, käytetään lajiteltuihin reunoihin i = 0 # Indeksimuuttuja, käytetään tulokseen[] e = 0 # Lajittele kaikki reunat # painonsa mukaan laskemattomaan # järjestykseen self.graph = lajiteltu(self.graph, key=lambda item: item[2]) vanhempi = [] sijoitus = [] # Luo V-osajoukkoja yksittäisillä elementeillä solmulle alueella(self.V): parent.append(node) rank.append(0) # Otettavien reunojen määrä on pienempi kuin V-1, kun taas 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->ei. kärkien & E->reunojen lukumäärä>>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>osajoukot[yroot].rank) subsets[yroot].parent = xroot; // Jos arvot ovat samat, tee yksi juuriksi // ja lisää sen arvoa yhdellä muulla { subsets[yroot].parent = xroot; osajoukot[xroot].rank++; } } // Pääfunktio MST:n rakentamiseen // käyttäen Kruskalin algoritmia void KruskalMST() { // Tämä tallentaa // tuloksena olevan MST Edge[] result = new Edge[V]; // Indeksimuuttuja, käytetään tulokselle[] int e = 0; // Indeksimuuttuja, jota käytetään lajiteltuihin reunoihin int i = 0; for (i = 0; i tulos[i] = new Edge(); // Lajittele kaikki reunat ei-laskevaan // painon mukaiseen järjestykseen. Jos emme saa // muuttaa annettua kuvaajaa, voimme luoda // kopio reunojen taulukosta Array.Sort(edge) // Varaa muistia V alijoukkojen luomiseen subset[] subsets = new subset [V] for (i = 0; i subsets[i] = new subset() // Luo V-osajoukkoja yksittäisillä elementeillä kohteelle (int v = 0; v osajoukot[v].parent = v; osajoukot[v].rank = 0; } i = 0; // Otettavien reunojen määrä on yhtä suuri to V-1 while (e // Valitse pienin reuna. Ja lisää // indeksiä seuraavalle iteraatiolle Edge next_edge = new Edge(); next_edge = edge[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest // Jos tämän reunan sisällyttäminen ei aiheuta sykliä, // sisällytä se tulokseen ja lisää seuraavan reunan indeksiä // if (x != y) {; result[e++] = next_edge; Union(subsets, x, y) rakennettu MST'); int minimiHinta = 0; for (i = 0; i Console.WriteLine(tulos[i].src + ' -- ' + tulos[i].kohde + ' == ' + tulos[i].paino); minimikustannukset += tulos[i].weight } Console.WriteLine('Minimum Cost Spanning Tree: ' + minimiCost. Console.ReadLine( } // Ohjaimen koodi public static void Main(String[] args); int V = 4 int E = 5; graph.edge[0].weight = 10; // lisää reuna 0-2 graph.edge[1].dest = 2; ; // lisää reuna 0-3 graafi.edge[2].dest = 3; edge[3].src = 1 graph.edge[3].weight = 15; lisää reuna 2-3 graafi .edge[4].dest = 3; graph.edge[4].weight = 4; // Funktiokutsu>
>// JavaScript implementation of the krushkal's algorithm.>>function>makeSet(parent,rank,n)>{>>for>