Algorithme d'arbre couvrant minimum de Kruskal - Algorithme gourmand en C++

Un arbre couvrant est un sous-graphe de graphe orienté non orienté qui relie tous les sommets. Il peut y avoir plusieurs arbres couvrants dans un graphique. L'arbre couvrant minimum (MST) sur chaque graphique a un poids identique ou inférieur à celui de tous les autres arbres couvrant. Des poids sont attribués aux arêtes du spanning tree, et la somme correspond au poids attribué à chaque arête. Puisque V est le nombre de sommets dans le graphe, l'arbre couvrant minimum a le nombre d'arêtes (V - 1), où V est le nombre d'arêtes.

Trouvez l'arbre couvrant minimum à l'aide de l'algorithme de Kruskal

• Tous les bords doivent être triés par ordre non décroissant par poids.

• Choisissez le plus petit côté. Si aucune boucle n'est formée, le bord est inclus.

• L'étape 2 doit être effectuée jusqu'à ce que l'arbre couvrant ait des bords (V-1).

Dans ce cas, on nous dit d'utiliser l'approche gourmande. L’option gourmande est de choisir le bord avec le plus petit poids. Par exemple : l'arbre couvrant minimum de ce graphique est (9-1) = 8 arêtes.

After sorting:

Weight  Src    Dest
21       27    26
22       28    22
22       26    25
24       20    21
24       22    25
26       28    26
27       22    23
27       27    28
28       20    27
28       21    22
29       23    24
30       25    24
31       21    27
34       23    25

Maintenant, nous devons sélectionner tous les bords en fonction du tri.

contient le bord 26-27->, car aucune boucle n'est formée

le bord comprend 28-22->, car aucune boucle n'est formée

comprend le bord 26-25->, car aucune boucle n'est formée.

Le bord 20-21-> est inclus car aucune boucle n'est formée.

Le bord 22-25-> est inclus car aucune boucle n'est formée.

Bord 28-26-> rejeté en raison de la formation de boucle

Bord 22-23-> > inclus car aucune boucle n'a été formée

Bord 27-28-> rejeté en raison de la formation de boucle

Bord 20 -27->Inclus car aucune boucle n'est formée

Bord 21-22->Rejeté car il forme une boucle

Bord 23-24->Inclus car aucune boucle n'est formée

Puisque le nombre d'arêtes est (V- 1), donc l'algorithme se termine ici.

Exemple

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Edge {
   int src, dest, weight;
};
struct Graph {
   int V, E;
   struct Edge* edge;
};
struct Graph* createGraph(int V, int E){
   struct Graph* graph = (struct Graph*)(malloc(sizeof(struct Graph)));
   graph->V = V;
   graph->E = E;
   graph->edge = (struct Edge*)malloc(sizeof( struct Edge)*E);
   return graph;
}
struct subset {
   int parent;
   int rank;
};
int find(struct subset subsets[], int i){
   if (subsets[i].parent != i)
      subsets[i].parent
   = find(subsets, subsets[i].parent);
   return subsets[i].parent;
}
void Union(struct subset subsets[], int x, int y){
   int xroot = find(subsets, x);
   int yroot = find(subsets, y);
   if (subsets[xroot].rank < subsets[yroot].rank)
      subsets[xroot].parent = yroot;
   else if (subsets[xroot].rank > subsets[yroot].rank)
      subsets[yroot].parent = xroot;
   else{
      subsets[yroot].parent = xroot;
      subsets[xroot].rank++;
   }
}
int myComp(const void* a, const void* b){
   struct Edge* a1 = (struct Edge*)a;
   struct Edge* b1 = (struct Edge*)b;
   return a1->weight > b1->weight;
}
void KruskalMST(struct Graph* graph){
   int V = graph->V;
   struct Edge
   result[V];
   int e = 0;
   int i = 0;
   qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
   struct subset* subsets
   = (struct subset*)malloc(V * sizeof(struct subset));
   for (int v = 0; v < V; ++v) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
   }
   while (e < V - 1 && i < graph->E) {
      struct Edge next_edge = graph->edge[i++];
      int x = find(subsets, next_edge.src);
      int y = find(subsets, next_edge.dest);
      if (x != y) {
         result[e++] = next_edge;
         Union(subsets, x, y);
      }
   }
   printf("Following are the edges in the constructed MST\n");
   int minimumCost = 0;
   for (i = 0; i < e; ++i){
      printf("%d -- %d == %d\n", result[i].src,
      result[i].dest, result[i].weight);
      minimumCost += result[i].weight;
   }
   printf("Minimum Cost Spanning tree : %d",minimumCost);
   return;
}
int main(){
   /* Let us create the following weighted graph
   30
   0--------1
   | \       |
   26| 25\ |15
   | \ |
   22--------23
   24 */
   int V = 24;
   int E = 25;
   struct Graph* graph = createGraph(V, E);
   graph->edge[0].src = 20;
   graph->edge[0].dest = 21;
   graph->edge[0].weight = 30;
   graph->edge[1].src = 20;
   graph->edge[1].dest = 22;
   graph->edge[1].weight = 26;
   graph->edge[2].src = 20;
   graph->edge[2].dest = 23;
   graph->edge[2].weight = 25;
   graph->edge[3].src = 21;
   graph->edge[3].dest = 23;
   graph->edge[3].weight = 35;
   graph->edge[4].src = 22;
   graph->edge[4].dest = 23;
   graph->edge[4].weight = 24;
   KruskalMST(graph);
   return 0;
}

Sortie

Following are the edges in the constructed MST
22 -- 23 == 24
20 -- 23 == 25
20 -- 21 == 30
Minimum Cost Spanning tree : 79

Conclusion

Ce tutoriel montre comment résoudre ce problème à l'aide de l'algorithme Minimum Spanning Tree de Kruskal - Méthode gourmande et du code C++. Nous pouvons également écrire ce code en Java, Python et d'autres langages. Il est calqué sur le concept de Kruskal. Ce programme trouve l'arbre couvrant le plus court dans un graphique donné. Nous espérons que vous avez trouvé ce tutoriel utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!