Un arbore care se întinde minim (MST) sau arborele de întindere cu greutate minimă pentru un grafic ponderat, conectat, nedirecționat este un arbore de întindere cu o greutate mai mică sau egală cu greutatea oricărui alt arbore de întindere. Pentru a afla mai multe despre Minimum Spanning Tree, consultați Acest articol .

Introducere în algoritmul lui Kruskal:

Aici vom discuta algoritmul lui Kruskal pentru a găsi MST-ul unui grafic ponderat dat.

În algoritmul lui Kruskal, sortați toate marginile graficului dat în ordine crescătoare. Apoi continuă să adauge noi margini și noduri în MST dacă marginea nou adăugată nu formează un ciclu. Alege marginea ponderată minimă la început și marginea ponderată maximă în cele din urmă. Astfel putem spune că face o alegere optimă local în fiecare pas pentru a găsi soluția optimă. Prin urmare, acesta este un Mai jos sunt pașii pentru găsirea MST folosind algoritmul lui Kruskal:

1. Sortați toate marginile în ordinea nedescrescătoare a greutății lor.
2. Alegeți cea mai mică margine. Verificați dacă formează un ciclu cu arborele de întindere format până acum. Dacă ciclul nu este format, includeți această margine. Altfel, aruncă-l.
3. Repetați pasul #2 până când există margini (V-1) în arborele de întindere.

Pasul 2 folosește Algoritmul Union-Find pentru a detecta ciclurile.

Așa că vă recomandăm să citiți următoarea postare ca o condiție prealabilă.

• Algoritmul Union-Find | Set 1 (Detectează ciclu într-un grafic)
• Algoritmul Unirii-Găsire | Setul 2 (Unirea după rang și comprimarea căii)

Algoritmul lui Kruskal pentru a găsi arborele de acoperire a costurilor minime folosește abordarea lacomă. Alegerea Greedy este de a alege cea mai mică margine de greutate care nu provoacă un ciclu în MST construit până acum. Să înțelegem cu un exemplu:

Ilustrare:

Mai jos este ilustrarea abordării de mai sus:

căutare binară în java

>

>

> 
    
număr în șir java
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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]: părinte[y] = x # Dacă rangurile sunt aceleași, atunci creați unul ca rădăcină # și creșteți rangul său cu alt rang: părinte[y] = x rang[x] += 1 # Funcția principală de construit MST # folosind algoritmul lui Kruskal def KruskalMST(self): # Acesta va stoca rezultatul MST rezultat = [] # O variabilă index, folosită pentru muchiile sortate i = 0 # O variabilă index, folosită pentru rezultat[] e = 0 # Sortați toate marginile în # ordinea nedescrescătoare a # greutății lor self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] # Creați V subseturi cu elemente individuale pentru nodul din interval(self.V): parent.append(node) rank.append(0) # Numărul de muchii care trebuie luate este mai mic decât V-1 în timp ce e
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
java citiți csv
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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->Nu. de vârfuri & E->nr.de muchii>>> 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].rank) subsets[yroot].parent = xroot;     // Dacă rangurile sunt aceleași, atunci creați unul ca rădăcină // și creșteți rangul cu unul else { subsets[yroot].parent = xroot;   subseturi[xroot].rank++;   } } // Funcția principală pentru a construi MST // folosind algoritmul lui Kruskal void KruskalMST() { // Aceasta va stoca // rezultatul MST Edge[] rezultat = new Edge[V];     // O variabilă index, folosită pentru result[] int e = 0;     // O variabilă index, folosită pentru muchiile sortate int i = 0;   for (i = 0; i result[i] = new Edge(); // Sortați toate muchiile în ordinea nedescrescătoare // a greutății lor. Dacă nu avem voie // să schimbăm graficul dat, putem crea // o copie a matricei de margini Array.Sort(edge) // Alocați memorie pentru crearea V subseturi subset[] subsets = new subset[V] for (i = 0; i subsets[i] = new subset()); ; // Creați V subseturi cu elemente simple pentru (int v = 0; v subseturi[v].parent = v; subseturi[v].rank = 0; } i = 0; // Numărul de muchii care trebuie luate este egal la V-1 while (e // Alegeți cea mai mică muchie. Și creșteți // indexul pentru următoarea iterație Edge next_edge = new Edge(); next_edge = edge[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest // Dacă includerea acestei margini nu provoacă ciclul, // includeți-o în rezultat și creșteți indicele // de rezultat pentru următoarea muchie if (x != y) { result[e++] = next_edge; Union(subsets, x, y) // Printează conținutul rezultat[] pentru a afișa // MST Console.WriteLine (Urmează marginile în ' + '); MST-ul construit');     int minimumCost = 0;   pentru (i = 0; i Console.WriteLine(rezultat[i].src + ' -- ' + rezultat[i].dest + ' == ' + rezultat[i].greutate); cost minim += rezultat[i].weight } Console.WriteLine('Arborele de acoperire a costurilor minime: ' + cost minim Console.ReadLine( } // Codul driverului public static void (String[] args)); int V = 4; int E = 5 Graph = new Graph(V, E) graph.edge[0].greutate = 10; ; // adaugă muchia 0-3 graph.edge[2].src = graph.edge[2].dest = graph.edge[2].weight = 5; edge[3].src = graph.edge[3].dest = graph.edge[3].weight = 15 graph.edge[4].src = 2; .edge[4].dest = 3; graph.edge[4].weight = 4;
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // JavaScript implementation of the krushkal's algorithm.> > function> makeSet(parent,rank,n)> {> >for>