Un arbre couvrant minimum (MST) ou arbre couvrant de poids minimum pour un graphique pondéré, connecté et non orienté est un arbre couvrant avec un poids inférieur ou égal au poids de tous les autres arbres couvrant. Pour en savoir plus sur l'arbre couvrant minimum, reportez-vous à Cet article .

Introduction à l'algorithme de Kruskal :

Nous discuterons ici L'algorithme de Kruskal pour trouver le MST d’un graphique pondéré donné.

Dans l'algorithme de Kruskal, triez toutes les arêtes du graphique donné par ordre croissant. Ensuite, il continue d'ajouter de nouvelles arêtes et nœuds dans le MST si l'arête nouvellement ajoutée ne forme pas un cycle. Il sélectionne d'abord le bord pondéré minimum et enfin le bord pondéré maximum. On peut donc dire qu'il fait un choix localement optimal à chaque étape afin de trouver la solution optimale. Il s'agit donc d'un Vous trouverez ci-dessous les étapes pour trouver MST à l’aide de l’algorithme de Kruskal :

1. Triez toutes les arêtes par ordre non décroissant de leur poids.
2. Choisissez le plus petit bord. Vérifiez s'il forme un cycle avec l'arbre couvrant formé jusqu'à présent. Si le cycle n'est pas formé, incluez cette arête. Sinon, jetez-le.
3. Répétez l'étape 2 jusqu'à ce qu'il y ait (V-1) arêtes dans l'arbre couvrant.

Étape 2 utilise le Algorithme Union-Find pour détecter les cycles.

Nous vous recommandons donc de lire le post suivant comme prérequis.

• Algorithme de recherche d'union | Ensemble 1 (Détecter le cycle dans un graphique)
• Algorithme de recherche d'union | Ensemble 2 (Union par rang et compression de chemin)

L'algorithme de Kruskal pour trouver l'arbre couvrant le coût minimum utilise l'approche gloutonne. Le choix gourmand consiste à choisir le plus petit bord de poids qui ne provoque pas de cycle dans le MST construit jusqu'à présent. Comprenons-le avec un exemple :

recherche binaire

>

>

> 
top 10 hentaï
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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] : parent[y] = x # Si les rangs sont identiques, alors créez-en un comme racine # et incrémentez son rang d'un autre : parent[y] = x rang[x] += 1 # La fonction principale à construire MST # en utilisant l'algorithme de Kruskal def KruskalMST(self): # Ceci stockera le résultat MST résultant = [] # Une variable d'index, utilisée pour les arêtes triées i = 0 # Une variable d'index, utilisée pour le résultat[] e = 0 # Trier toutes les arêtes dans # l'ordre non décroissant de leur # poids self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] Rank = [] # Créer des sous-ensembles en V avec des éléments uniques pour le nœud dans la plage (self.V) : parent.append (node) Rank.append (0) # Le nombre d'arêtes à prendre est inférieur à V-1 tandis que e
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
ymail
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // 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->Non. de sommets & E->nombre d'arêtes> >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>sous-ensembles[yroot].rank) sous-ensembles[yroot].parent = xroot;     // Si les rangs sont identiques, créez-en un en tant que racine // et incrémentez son rang d'un autre { subsets[yroot].parent = xroot;   sous-ensembles[xroot].rank++;   } } // La fonction principale pour construire MST // en utilisant l'algorithme de Kruskal void KruskalMST() { // Ceci stockera le // MST Edge[] résultant result = new Edge[V];     // Une variable d'index, utilisée pour result[] int e = 0;     // Une variable d'index, utilisée pour les arêtes triées int i = 0;   for (i = 0; i result[i] = new Edge(); // Trie toutes les arêtes dans // l'ordre non décroissant de leur poids. Si nous ne sommes pas autorisés // à modifier le graphique donné, nous pouvons créer // une copie du tableau d'arêtes Array.Sort(edge); // Allouer de la mémoire pour créer des sous-ensembles V subset[] subsets = new subset[V]; ; // Crée des sous-ensembles V avec des éléments uniques pour (int v = 0; v subsets[v].parent = v; subsets[v].rank = 0; } i = 0; // Le nombre d'arêtes à prendre est égal à V-1 while (e // Choisissez le plus petit bord. Et incrémentez // l'index pour la prochaine itération Edge next_edge = new Edge(); next_edge = edge[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest); // Si l'inclusion de cette arête ne provoque pas de cycle, // incluez-la dans le résultat et incrémentez l'index // du résultat pour l'arête suivante if (x != y) { result[e++] = next_edge; Union(subsets, x, y); } } // Imprime le contenu de result[] pour afficher // la console MST construite.WriteLine('Voici les bords dans ' + ' le MST construit');     int coût minimum = 0 ;   pour (i = 0; i Console.WriteLine(result[i].src + ' -- ' + result[i].dest + ' == ' + result[i].weight); minimumCost += result[i].weight; } Console.WriteLine('Arbre couvrant le coût minimum : ' + minimumCost(); } // Code du pilote public static void Main(String[] args) { int V = 4; int E = 5; Graph graph = new Graph(V, E); // ajoute le bord 0-1 graph.edge[0].src = 0; graph.edge[0].weight = 10; // ajouter le bord 0-2 graph.edge[1].src = 0; graph.edge[1].dest = 2; ; // ajoute le bord 0-3 graph.edge[2].src = 0; graph.edge[2].dest = 3; graph.edge[2].weight = 5; edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 15; // ajouter le bord 2-3 graph.edge[4].src = 2; .edge[4].dest = 3; graph.edge[4].weight = 4; // Appel de fonction graph.KruskalMST(); } } // Ce code est fourni par Aakash Hasija>
 
 
 
 
    
 
>
 
    
 
>
 
 
Javascript
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > // 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)=>{ retourner a[2] - b[2];   }) //La fonction de tri rapide intégrée est fournie avec stdlib.h //allez sur https://www.techcodeview.com Le tri des bords prend un temps O(E * logE).  Après le tri, nous parcourons toutes les arêtes et appliquons l'algorithme de recherche d'union. Les opérations de recherche et d'union peuvent prendre au plus un temps O(logV). La complexité globale est donc le temps O(E * logE + E * logV).  La valeur de E peut être au plus O(V2), donc O(logV) et O(logE) sont identiques. Par conséquent, la complexité temporelle globale est O(E * logE) ou O(E*logV) Espace auxiliaire : O(V + E), où V est le nombre de sommets et E est le nombre d'arêtes dans le graphique. Cet article est compilé par Aashish Barnwal et révisé par l'équipe techcodeview.com.>