Et minimum spenntre (MST) eller minimumsvektspenningstre for en vektet, koblet, urettet graf er et spenntre med en vekt som er mindre enn eller lik vekten til hvert annet spenntre. For å lære mer om Minimum Spanning Tree, se denne artikkelen .

Introduksjon til Kruskals algoritme:

Her skal vi diskutere Kruskals algoritme for å finne MST for en gitt vektet graf.

I Kruskals algoritme, sorter alle kantene på den gitte grafen i økende rekkefølge. Deretter fortsetter den å legge til nye kanter og noder i MST hvis den nylig lagt til kanten ikke danner en syklus. Den velger den minste vektede kanten først og den maksimalt vektede kanten til slutt. Dermed kan vi si at den gjør et lokalt optimalt valg i hvert trinn for å finne den optimale løsningen. Derfor er dette en Nedenfor er trinnene for å finne MST ved å bruke Kruskals algoritme:

1. Sorter alle kantene i ikke-avtagende rekkefølge etter vekt.
2. Velg den minste kanten. Sjekk om det danner en syklus med spenntreet som er dannet så langt. Hvis syklusen ikke er dannet, inkluderer denne kanten. Ellers, kast den.
3. Gjenta trinn 2 til det er (V-1) kanter i spenntreet.

Steg 2 bruker Union-Find-algoritme for å oppdage sykluser.

Så vi anbefaler å lese følgende innlegg som en forutsetning.

• Union-Find Algoritme | Sett 1 (Oppdag syklus i en graf)
• Union-Find Algoritme | Sett 2 (Union by Rank and Path Compression)

Kruskals algoritme for å finne minimumskostnadsspenningstreet bruker den grådige tilnærmingen. Det grådige valget er å velge den minste vektkanten som ikke forårsaker en syklus i MST konstruert så langt. La oss forstå det med et eksempel:

Illustrasjon:

Nedenfor er illustrasjonen av tilnærmingen ovenfor:

kvikksortering

>

>

java design mønstre

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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 sortere en matrise 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]: overordnet[y] = x # Hvis rekkene er like, lag en som rot # og øk rangeringen med en annen: forelder[y] = x rang[x] += 1 # Hovedfunksjonen for å konstruere MST # bruker Kruskals algoritme def KruskalMST(selv): # Dette vil lagre det resulterende MST-resultatet = [] # En indeksvariabel, brukt for sorterte kanter i = 0 # En indeksvariabel, brukt for resultat[] e = 0 # Sorter alle kantene i # ikke-avtagende rekkefølge av deres # vekt self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] # Lag V-delsett med enkeltelementer for node in range(self.V): parent.append(node) rank.append(0) # Antall kanter som skal tas er mindre enn 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->Nei. av hjørner & E->antall 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>delsett[yroot].rang) delsett[yroot].parent = xroot;     // Hvis rangeringene er like, lag en som root // og øk rangeringen med en annen { subsets[yroot].parent = xroot;   delsett[xroot].rang++;   } } // Hovedfunksjonen for å konstruere MST // ved å bruke Kruskals algoritme void KruskalMST() { // Dette vil lagre // resulterende MST Edge[]-resultat = new Edge[V];     // En indeksvariabel, brukt for resultat[] int e = 0;     // En indeksvariabel, brukt for sorterte kanter int i = 0;   for (i = 0; i result[i] = new Edge(); // Sorter alle kantene i ikke-avtagende // rekkefølge etter vekt. Hvis vi ikke har lov til // å endre den gitte grafen, kan vi lage // en kopi av array of edges Array.Sort(edge) // Alloker minne for å lage V-delsett[]-delsett = nytt undersett[V] for (i = 0; i undersett() ; // Lag V delsett med enkeltelementer for (int v = 0; v delsett[v].parent = v; delsett[v].rang = 0; } i = 0; // Antall kanter som skal tas er likt til V-1 while (e // Velg den minste kanten. Og øk // indeksen for neste iterasjon 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 kanten ikke forårsaker syklus, // inkluderer den i resultatet og øker indeksen // av resultatet for neste kant hvis (x != y) { result[e++] = next_edge (undersett, x, y } } // Skriv ut innholdet i resultatet[] for å vise // den innebygde MST Console.WriteLine('Følger er kantene i ' + '); den konstruerte MST');     int minimumCost = 0;   for (i = 0; i Console.WriteLine(result[i].src + ' -- ' + result[i].dest + ' == ' + resultat[i].weight); minimumCost += result[i].weight; } Console.WriteLine('Minimum Cost Spanning Tree: ' + minimumCost) Console.ReadLine(); 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 koden er bidratt av Aakash Hasija>
 
 
 
 
    
 
>
 
    
 
>
 
 
Javascript
    
np polstring
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // 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];   }) //innebygd hurtigsorteringsfunksjon kommer med stdlib.h //gå til https://www.techcodeview.com Sortering av kanter tar O(E * logE) tid.  Etter sortering, itererer vi gjennom alle kanter og bruker finn-union-algoritmen. Funn- og foreningsoperasjonene kan ta maksimalt O(logV) tid. Så generell kompleksitet er O(E * logE + E * logV) tid.  Verdien av E kan maksimalt være O(V2), så O(logV) og O(logE) er like. Derfor er den totale tidskompleksiteten O(E * logE) eller O(E*logV) Auxiliary Space: O(V + E), der V er antall toppunkter og E er antall kanter i grafen. Denne artikkelen er kompilert av Aashish Barnwal og gjennomgått av techcodeview.com-teamet.>