Un arbre allargat mínim (MST) o arbre allargat de pes mínim per a un gràfic ponderat, connectat i no dirigit és un arbre abastant amb un pes inferior o igual al pes de qualsevol altre arbre spanning. Per obtenir més informació sobre Minimum Spanning Tree, consulteu Aquest article .
Introducció a l'algoritme de Kruskal:
Aquí en parlarem algorisme de Kruskal per trobar el MST d'un gràfic ponderat donat.
En l'algorisme de Kruskal, ordena totes les vores del gràfic donat en ordre creixent. A continuació, continua afegint noves vores i nodes a l'MST si la vora afegida no forma un cicle. Tria la vora ponderada mínima al principi i la vora ponderada màxima finalment. Així, podem dir que fa una elecció localment òptima en cada pas per tal de trobar la solució òptima. Per tant, això és un A continuació es mostren els passos per trobar MST mitjançant l'algorisme de Kruskal:
- Ordena totes les vores en ordre no decreixent del seu pes.
- Trieu la vora més petita. Comproveu si forma un cicle amb l'arbre spanning format fins ara. Si el cicle no està format, inclou aquesta vora. En cas contrari, descarta-ho.
- Repetiu el pas 2 fins que hi hagi vores (V-1) a l'arbre allargat.
Pas 2 utilitza el Algorisme Union-Find per detectar cicles.
Per tant, us recomanem que llegiu la següent publicació com a requisit previ.
- Algoritme Union-Find | Conjunt 1 (detecció de cicle en un gràfic)
- Algoritme Union-Find | Set 2 (Unió per rang i compressió de camí)
L'algoritme de Kruskal per trobar l'arbre que abasta el cost mínim utilitza l'enfocament cobdiciós. L'elecció Greedy és triar la vora de pes més petita que no provoqui un cicle en el MST construït fins ara. Entenem-ho amb un exemple:
Il·lustració:
A continuació es mostra la il·lustració de l'enfocament anterior:
Gràfic d'entrada:
El gràfic conté 9 vèrtexs i 14 arestes. Per tant, l'arbre allargat mínim format tindrà (9 – 1) = 8 vores.
Després d'ordenar:
Pes Font Destinació 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 11 1 7 14 3 5 Ara trieu totes les vores una per una de la llista ordenada d'arestes
Pas 1: Trieu la vora 7-6. No es forma cap cicle, inclou-lo.
Afegiu la vora 7-6 a l'MST
Pas 2: Tria la vora 8-2. No es forma cap cicle, inclou-lo.
Afegiu la vora 8-2 al MST
Pas 3: Trieu la vora 6-5. No es forma cap cicle, inclou-lo.
Afegiu la vora 6-5 al MST
Pas 4: Tria la vora 0-1. No es forma cap cicle, inclou-lo.
Afegiu la vora 0-1 a l'MST
Pas 5: Trieu la vora 2-5. No es forma cap cicle, inclou-lo.
Afegiu la vora 2-5 al MST
Pas 6: Trieu la vora 8-6. Com que incloure aquesta vora resulta en el cicle, descarteu-lo. Trieu la vora 2-3: No es forma cap cicle, inclou-lo.
teoria d'arbres i grafsAfegiu la vora 2-3 al MST
Pas 7: Trieu la vora 7-8. Com que incloure aquesta vora resulta en el cicle, descarteu-lo. Tria la vora 0-7. No es forma cap cicle, inclou-lo.
Afegeix la vora 0-7 a MST
Pas 8: Trieu la vora 1-2. Com que incloure aquesta vora resulta en el cicle, descarteu-lo. Trieu la vora 3-4. No es forma cap cicle, inclou-lo.
Afegiu la vora 3-4 al MST
Nota: Com que el nombre d'arestes incloses a l'MST és igual a (V - 1), l'algorisme s'atura aquí
A continuació es mostra la implementació de l'enfocament anterior:
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]) { pare[s2] = s1; } else { pare[s2] = s1; rang[s1] += 1; } } } }; class Graph { vectorint>> edgelist; int V; public: Graph(int V) { this->V = V; } // Funció per afegir vora en un gràfic void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() { // Ordena totes les vores sort(edgelist.begin(), edgelist.end()); // Inicialitzar la 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]) { pare[v] = u; } else { pare[v] = u; // Com que el rang augmenta si // els rangs de dos conjunts tenen el mateix rang[u]++; } } // Funció per trobar el MST void kruskalAlgo(int n, int edge[n][3]) { // Primer ordenem la matriu de vores en ordre ascendent // de manera que puguem accedir a les distàncies mínimes/cost qsort(edge , n, sizeof(edge[0]), comparador); int pare[n]; rang int [n]; // Funció per inicialitzar parent[] i rank[] makeSet(parent, rank, n); // Per emmagatzemar el cost mínim int minCost = 0; printf('A continuació es mostren les vores del MST construït
'); for (int i = 0; i int v1 = findParent (pare, vora[i][0]); int v2 = findParent (pare, vora[i][1]); int wt = vora[i][2] ; // Si els pares són diferents, això // significa que estan en conjunts diferents, així que // uneix-los if (v1 != v2) { unionSet(v1, v2, parent, rank, n; '%d -- %d == %d
', vora[i][0], vora[i][1], wt } } printf('Arbre d'abast mínim: %d); n', minCost); } // Codi del controlador 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>>>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]>rang[y]: pare[y] = x # Si els rangs són els mateixos, feu-ne un com a arrel # i incrementeu el seu rang en un altre: pare[y] = x rang[x] += 1 # La funció principal a construir MST # utilitzant l'algorisme de Kruskal def KruskalMST(self): # Això emmagatzemarà el resultat MST resultant = [] # Una variable d'índex, utilitzada per a les vores ordenades i = 0 # Una variable d'índex, utilitzada per al resultat[] e = 0 # Ordena totes les vores en # ordre no decreixent del seu # pes self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] # Crea subconjunts V amb elements individuals per al node dins l'interval (self.V): parent.append (node) rank.append (0) # El nombre d'arestes a prendre és inferior a V-1 mentre que 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->no. de vèrtexs & E->núm.d'arestes>>>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>subconjunts[yroot].rank) subconjunts[yroot].parent = xroot; // Si els rangs són els mateixos, feu-ne un com a arrel // i n'augmenteu el rang en un altre { subconjunts[yroot].parent = xroot; subconjunts[xroot].rank++; } } // La funció principal per construir MST // utilitzant l'algorisme de Kruskal void KruskalMST() { // Això emmagatzemarà el // resultat MST Edge[] resultat = new Edge[V]; // Una variable d'índex, utilitzada per resultat[] int e = 0; // Una variable d'índex, utilitzada per a les vores ordenades int i = 0; for (i = 0; i resultat[i] = new Edge(); // Ordena totes les arestes en // ordre no decreixent del seu pes. Si no podem // canviar el gràfic donat, podem crear // una còpia de la matriu d'arestes Array.Sort(edge) // Assigna memòria per a la creació de subconjunts V subconjunt[] subconjunts = nou subconjunt[V] per (i = 0; i subconjunt[i] = subconjunt nou()); ; // Crea V subconjunts amb elements individuals per a (int v = 0; v subconjunts[v].parent = v; subconjunts[v].rank = 0; } i = 0; // El nombre d'arestes a prendre és igual a V-1 mentre (e // Trieu la vora més petita. I incrementeu // l'índex per a la següent iteració Edge next_edge = new Edge(); next_edge = edge[i++]; int x = find(subconjunts, next_edge.src); int y = find(subsets, next_edge.dest // Si incloure aquesta vora no provoca cicle, // inclou-la al resultat i augmenta l'índex // del resultat per a la vora següent if (x != y) { resultat[e++] = next_edge; Union(subconjunts, x, y } } // Imprimeix el contingut del resultat[] per mostrar // la consola MST integrada. el MST construït'); int cost mínim = 0; per a (i = 0; i Console.WriteLine(resultat[i].src + ' -- ' + resultat[i].dest + ' == ' + resultat[i].pes); cost mínim += resultat[i].weight } Console.WriteLine('Minimum Cost Spanning Tree: ' + minimumCost Console.ReadLine(}) // Codi del controlador public static void (String[] args); int V = 4; int E = 5 Graph graph = new Graph(V, E) // suma graph.edge[0].src = 1; graph.edge[0].weight = 10; // afegeix edge 0-2 graph.edge[1].src = graph.edge[1].dest = 2; ; // afegeix vora 0-3 graph.edge[2].src = graph.edge[2].dest = graph.edge[2].weight = 5; edge[3].src = 1; graph.edge[3].dest = graph.edge[3].weight = 15; graph.edge[4].src = 2; .edge[4].dest = 3; graph.edge[4].weight = 4 // Crida a la funció graph.KruskalMST( } } // Aquest codi és aportat per Aakash Hasija>'>);>Kat timpf
>// JavaScript implementation of the krushkal's algorithm.>>function>makeSet(parent,rank,n)>{>>for>>>