Mažiausiai besitęsiantis medis (MST) arba minimalaus svorio apimantis medis, skirtas svertiniam, sujungtam, nenukreiptam grafikui, yra apimantis medis, kurio svoris mažesnis arba lygus kiekvieno kito apimančio medžio svoriui. Norėdami sužinoti daugiau apie minimalų besitęsiantį medį, žr Šis straipsnis .
Kruskal algoritmo įvadas:
Čia mes aptarsime Kruskal algoritmas norėdami rasti nurodyto svertinio grafiko MST.
Kruskal algoritme surūšiuokite visas nurodyto grafiko briaunas didėjančia tvarka. Tada jis toliau prideda naujų kraštų ir mazgų į MST, jei naujai pridėtas kraštas nesudaro ciklo. Iš pradžių jis pasirenka mažiausią svertinį kraštą ir galiausiai didžiausią svertinį kraštą. Taigi galime teigti, kad kiekviename žingsnyje jis daro lokaliai optimalų pasirinkimą, kad rastų optimalų sprendimą. Taigi tai yra a Toliau pateikiami žingsniai, kaip rasti MST naudojant Kruskal algoritmą:
- Surūšiuokite visus kraštus nemažėjančia tvarka pagal jų svorį.
- Pasirinkite mažiausią kraštą. Patikrinkite, ar jis sudaro ciklą su iki šiol suformuotu apimančiu medžiu. Jei ciklas nesusiformavęs, įtraukite šį kraštą. Kitu atveju išmeskite.
- Kartokite 2 veiksmą, kol aprėpiančiame medyje atsiras (V-1) briaunos.
2 žingsnis naudoja Union-Find algoritmas aptikti ciklus.
Operacinė sistemaTaigi rekomenduojame perskaityti šį įrašą kaip būtinąją sąlygą.
- Sąjungos paieškos algoritmas | 1 rinkinys (aptikti ciklą diagramoje)
- Sąjungos paieškos algoritmas | 2 rinkinys (sujungimas pagal rangą ir kelio suspaudimą)
Kruskal algoritmas, skirtas rasti minimalias išlaidas apimantį medį, naudoja godų metodą. Greedy Choice yra pasirinkti mažiausią svorio kraštą, kuris nesukelia ciklo iki šiol sukonstruotoje MST. Supraskime tai pavyzdžiu:
Iliustracija:
Žemiau yra aukščiau pateikto požiūrio iliustracija:
Įvesties grafikas:
Grafike yra 9 viršūnės ir 14 briaunų. Taigi suformuotas minimalus apimantis medis bus (9 – 1) = 8 briaunos.
Po rūšiavimo:
Svoris Šaltinis Kelionės tikslas 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 vienuolika 1 7 14 3 5 Dabar pasirinkite visus kraštus po vieną iš surūšiuoto kraštų sąrašo
1 žingsnis: Pasirinkite 7-6 kraštą. Ciklas nesusidaro, įtraukite jį.
Pridėkite 7–6 kraštą MST
2 žingsnis: Paimkite kraštą 8-2. Ciklas nesusidaro, įtraukite jį.
Pridėkite 8-2 kraštą MST
3 veiksmas: Pasirinkite 6-5 kraštą. Ciklas nesusidaro, įtraukite jį.
Pridėkite 6-5 kraštą MST
4 veiksmas: Pasirinkimas 0-1. Ciklas nesusidaro, įtraukite jį.
Pridėkite kraštą 0-1 MST
5 veiksmas: Pasirinkite 2-5 kraštą. Ciklas nesusidaro, įtraukite jį.
Pridėkite 2–5 kraštą MST
6 veiksmas: Pasirinkite 8-6 kraštą. Kadangi įtraukus šį kraštą atsiranda ciklas, išmeskite jį. Pasirinkite 2–3 kraštą: Ciklas nesusidaro, įtraukite jį.
Pridėkite 2–3 kraštą MST
7 veiksmas: Pasirinkite 7-8 kraštą. Kadangi įtraukus šį kraštą atsiranda ciklas, išmeskite jį. Pasirinkimo kraštas 0-7. Ciklas nesusidaro, įtraukite jį.
Pridėkite kraštą 0–7 MST
8 veiksmas: Pasirinkite 1-2 kraštą. Kadangi įtraukus šį kraštą atsiranda ciklas, išmeskite jį. Pasirinkite 3-4 kraštą. Ciklas nesusidaro, įtraukite jį.
Pridėkite 3–4 kraštą MST
Pastaba: Kadangi į MST įtrauktų briaunų skaičius lygus (V – 1), algoritmas čia sustoja
Toliau pateikiamas pirmiau minėto metodo įgyvendinimas:
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]>rangas[s2]) { tėvas[s2] = s1; } else { tėvas[s2] = s1; rangas[s1] += 1; } } } }; class Graph { vectorint>> edgelist; int V; public: Grafas(int V) { this->V = V; } // Funkcija pridėti briauną grafe void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() { // Rūšiuoti visus kraštus sort(edgelist.begin(), edgelist.end()); // Inicijuoti 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]>rangas[v]) { tėvas[v] = u; } else { tėvas[v] = u; // Kadangi rangas didėja, jei // dviejų aibių eilės yra vienodos rangas[u]++; } } // Funkcija rasti MST void kruskalAlgo(int n, int edge[n][3]) { // Pirmiausia surūšiuojame briaunų masyvą didėjančia tvarka // kad galėtume pasiekti minimalius atstumus/kainą qsort(edge , n, dydis(kraštas[0]), lyginamoji priemonė); int parent[n]; int rangas[n]; // Funkcija inicijuoti pirminį[] ir rangą[] makeSet(parent, rangas, n); // Minimalių sąnaudų saugojimui int minCost = 0; printf( 'Toliau pateikiamos sukurtos MST briaunos
'); for (int i = 0; i int v1 = rastiParent(pirminis, kraštas[i][0]); int v2 = rastiParent(parent, kraštas[i][1]); int wt = kraštas[i][2] // Jei tėvai yra skirtingi, tai // reiškia, kad jie yra skirtinguose rinkiniuose, taigi // sujunkite juos if (v1, v2, parent, rank, n); '%d -- %d == %d
', kraštas[i][0], kraštas[i][1], wt } } printf('Minimalių sąnaudų medis: %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>>>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]>rangas[y]: pirminis[y] = x # Jei rangai yra vienodi, tada vieną padarykite kaip šaknį # ir padidinkite jo rangą vienu kitu: pirminis[y] = x rangas[x] += 1 # Pagrindinė kūrimo funkcija MST # naudojant Kruskal algoritmą def KruskalMST(self): # Tai išsaugos gautą MST rezultatą = [] # Indekso kintamasis, naudojamas surūšiuotiems kraštams i = 0 # Indekso kintamasis, naudojamas rezultatui[] e = 0 # Rūšiuoti visus kraštus # nemažėjančia tvarka pagal jų svorį self.graph = surūšiuota(self.graph, key=lambda item: item[2]) pirminis = [] rangas = [] # Sukurkite V poaibius su atskirais elementais mazgui diapazone(self.V): parent.append(node) rank.append(0) # Kraštinių skaičius, kurį reikia paimti, yra mažesnis nei V-1, 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->ne. viršūnių & E->kraštinių skaičius>>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>subaibiai[yroot].rank) subsets[yroot].parent = xroot; // Jei rangai yra vienodi, padarykite vieną kaip šaknį // ir padidinkite jo rangą dar vienu { subsets[yroot].parent = xroot; poaibiai[xroot].rank++; } } // Pagrindinė funkcija sukurti MST // naudojant Kruskal's algoritmą void KruskalMST() { // Tai išsaugos // gautą MST Edge[] rezultatą = new Edge[V]; // Indekso kintamasis, naudojamas rezultatui[] int e = 0; // Indekso kintamasis, naudojamas surūšiuotiems kraštams int i = 0; for (i = 0; i rezultatas[i] = new Edge(); // Surūšiuoti visas briaunas nemažėjančia // jų svorio tvarka. Jei mums neleidžiama // keisti duoto grafiko, galime sukurti // briaunų masyvo kopija Array.Sort(edge) // Skirti atmintį V subsets subset [] subsets = new subset[V] for (i = 0; i subsets[i] = new subset() // Sukurkite V poaibius su atskirais elementais (int v = 0; v poaibiai[v].parent = v; poaibiai[v].rank = 0; } i = 0; // Paimtinų briaunų skaičius yra lygus į V-1 while (e // Pasirinkite mažiausią kraštą. Ir padidinkite // kitos iteracijos indeksą Edge next_edge = new Edge(); next_edge = kraštas[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest) // Jei įtraukus šią briauną, ciklas nesukeliamas, // įtraukite jį į rezultatą ir padidinkite kito krašto rezultato indeksą // if (x != y) { result[e++] = next_edge; pogrupiai, x, y; pastatytas MST'); int minimaliKaina = 0; for (i = 0; i Console.WriteLine(rezultatas[i].src + ' -- ' + rezultatas[i].destalas + ' == ' + rezultatas[i].svoris); minimali kaina += rezultatas[i].weight } Console.WriteLine('Minimum Cost Spanning Tree: ' + minimalCost Console.ReadLine( } // Tvarkyklės kodas public static void Main(String[] args)); int V = 4; Graph graph = naujas Grafas(V, E) grafas.kraštas[0].svoris = 10; // pridėti kraštas 0-2 grafas.kraštas[1].destas = 2; ; // pridėti kraštas 0-3 grafas. kraštas[2].dest = 3; kraštas[3].src = 1 grafas.kraštas[3].svoris = 15; .edge[4].dest = 3; graph.edge[4].weight = 4; // Funkcijos iškvietimo grafikas>
>// JavaScript implementation of the krushkal's algorithm.>>function>makeSet(parent,rank,n)>{>>for>