Algorithme Boruvka en C++ pour un arbre couvrant minimum

Dans la théorie des graphes, trouver l'arbre couvrant minimum (MST) d'un graphe pondéré connecté est un problème courant. MST est un sous-ensemble d'arêtes de graphique qui relie tous les sommets et minimise le poids total des arêtes. Un algorithme efficace pour résoudre ce problème est l’algorithme de Boruvka.

Grammaire

struct Edge {
   int src, dest, weight;
};

// Define the structure to represent a subset for union-find
struct Subset {
   int parent, rank;
};

Algorithme

Maintenant, décrivons les étapes à suivre pour trouver l'arbre couvrant minimum dans l'algorithme de Boruvka −

• Initialisez MST sur l'ensemble vide.

• Créez un sous-ensemble pour chaque sommet, où chaque sous-ensemble ne contient qu'un seul sommet.

• Répétez les étapes suivantes jusqu'à ce que l'arbre couvrant minimum (MST) ait des arêtes V-1 (V est le nombre de sommets dans le graphique) −

  • Pour chaque sous-ensemble, trouvez l'arête la moins chère le reliant à l'autre sous-ensemble.

  • Ajoutez les arêtes sélectionnées à un arbre couvrant minimum.

  • Effectuez une opération d'union sur un sous-ensemble d'arêtes sélectionnées.

• Sortez l'arbre couvrant minimum.

Méthode

Dans l'algorithme de Boruvka, il existe plusieurs façons de trouver l'arête la moins chère reliant chaque sous-ensemble. Voici deux méthodes courantes −

Méthode 1 : Méthode simple

Pour chaque sous-ensemble, parcourez toutes les arêtes et trouvez la plus petite arête le reliant à l'autre sous-ensemble.

Suivez les arêtes sélectionnées et effectuez des opérations conjointes.

Exemple

#include <iostream>
#include <vector>
#include <algorithm>

struct Edge {
   int src, dest, weight;
};

// Define the structure to represent a subset for union-find
struct Subset {
   int parent, rank;
};

// Function to find the subset of an element using path compression
int find(Subset subsets[], int i) {
   if (subsets[i].parent != i)
      subsets[i].parent = find(subsets, subsets[i].parent);
   return subsets[i].parent;
}

// Function to perform union of two subsets using union by rank
void unionSets(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++;
   }
}

// Function to find the minimum spanning tree using Boruvka's algorithm
void boruvkaMST(std::vector<Edge>& edges, int V) {
   std::vector<Edge> selectedEdges; // Stores the edges of the MST

   Subset* subsets = new Subset[V];
   int* cheapest = new int[V];

   // Initialize subsets and cheapest arrays
   for (int v = 0; v < V; v++) {
      subsets[v].parent = v;
      subsets[v].rank = 0;
      cheapest[v] = -1;
   }

   int numTrees = V;
   int MSTWeight = 0;

   // Keep combining components until all components are in one tree
   while (numTrees > 1) {
      for (int i = 0; i < edges.size(); i++) {
         int set1 = find(subsets, edges[i].src);
         int set2 = find(subsets, edges[i].dest);

         if (set1 != set2) {
            if (cheapest[set1] == -1 || edges[cheapest[set1]].weight > edges[i].weight)
               cheapest[set1] = i;
            if (cheapest[set2] == -1 || edges[cheapest[set2]].weight > edges[i].weight)
               cheapest[set2] = i;
         }
      }

      for (int v = 0; v < V; v++) {
         if (cheapest[v] != -1) {
            int set1 = find(subsets, edges[cheapest[v]].src);
            int set2 = find(subsets, edges[cheapest[v]].dest);

            if (set1 != set2) {
               selectedEdges.push_back(edges[cheapest[v]]);
               MSTWeight += edges[cheapest[v]].weight;
               unionSets(subsets, set1, set2);
               numTrees--;
            }

            cheapest[v] = -1;
         }
      }
   }

   // Output the MST weight and edges
   std::cout << "Minimum Spanning Tree Weight: " << MSTWeight << std::endl;
   std::cout << "Selected Edges:" << std::endl;
   for (const auto& edge : selectedEdges) {
      std::cout << edge.src << " -- " << edge.dest << " \tWeight: " << edge.weight << std::endl;
   }

   delete[] subsets;
   delete[] cheapest;
}

int main() {
   // Pre-defined input for testing purposes
   int V = 6;
   int E = 9;
   std::vector<Edge> edges = {
      {0, 1, 4},
      {0, 2, 3},
      {1, 2, 1},
      {1, 3, 2},
      {1, 4, 3},
      {2, 3, 4},
      {3, 4, 2},
      {4, 5, 1},
      {2, 5, 5}
   };

   boruvkaMST(edges, V);

   return 0;
}

Sortie

Minimum Spanning Tree Weight: 9
Selected Edges:
0 -- 2 	Weight: 3
1 -- 2 	Weight: 1
1 -- 3 	Weight: 2
4 -- 5 	Weight: 1
3 -- 4 	Weight: 2

La traduction chinoise de

Explication

est :

Explication

Nous définissons d'abord deux structures - Edge et Subset. Edge représente une arête dans le graphique, y compris la source, la destination et le poids de l'arête. Le sous-ensemble représente un sous-ensemble de la structure de données de la requête Union, comprenant les informations sur le parent et le classement.

La fonction find est une fonction d'assistance qui utilise la compression de chemin pour trouver un sous-ensemble d'éléments. Il trouve récursivement les représentants (nœuds parents) du sous-ensemble auquel appartient l'élément et compresse le chemin pour optimiser les requêtes futures.

La fonction

unionSets est une autre fonction auxiliaire qui fusionne deux sous-ensembles en utilisant la fusion par rang. Il trouve des représentants de deux sous-ensembles et les fusionne en fonction de leur rang pour maintenir un arbre équilibré.

La fonction

boruvkaMST prend en entrée un vecteur d'arête et un nombre de sommets (V). Il implémente l'algorithme Boruvka pour trouver MST.

Dans la fonction boruvkaMST, nous créons un vecteur selectedEdges pour stocker les bords de MST.

Nous créons un tableau de structures de sous-ensembles pour représenter les sous-ensembles et les initialisons avec des valeurs par défaut.

Nous créons également un tableau le moins cher pour garder une trace de l'avantage le moins cher pour chaque sous-ensemble.

La variable numTrees est initialisée au nombre de sommets et MSTWeight est initialisée à 0.

L'algorithme fonctionne en combinant à plusieurs reprises des composants jusqu'à ce que tous les composants soient dans un arbre. La boucle principale s'exécute jusqu'à ce que numTrees devienne 1.

À chaque itération de la boucle principale, nous parcourons toutes les arêtes et trouvons l'arête pondérée minimale pour chaque sous-ensemble. Si une arête connecte deux sous-ensembles différents, nous mettons à jour le tableau le moins cher avec l'indice de l'arête la moins pondérée.

Ensuite, nous parcourons tous les sous-ensembles. Si un sous-ensemble a une arête avec un poids minimum, nous l'ajoutons au vecteur selectedEdges, mettons à jour MSTWeight, effectuons l'opération d'union des sous-ensembles et réduisons la valeur de numTrees.

Enfin, nous générons les poids MST et les arêtes sélectionnées.

La fonction principale invite l'utilisateur à saisir le nombre de sommets et d'arêtes. Il prend ensuite l'entrée (source, cible, poids) pour chaque bord et appelle la fonction boruvkaMST avec l'entrée.

Méthode 2 : Utiliser la file d'attente prioritaire

Créez une file d'attente prioritaire triée par poids pour stocker les bords.

Pour chaque sous-ensemble, recherchez le bord de poids minimum le reliant à un autre sous-ensemble de la file d'attente prioritaire.

Suivez les arêtes sélectionnées et effectuez des opérations conjointes.

Exemple

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// Edge structure representing a weighted edge in the graph
struct Edge {
   int destination;
   int weight;

   Edge(int dest, int w) : destination(dest), weight(w) {}
};

// Function to find the shortest path using Dijkstra's algorithm
vector<int> dijkstra(const vector<vector<Edge>>& graph, int source) {
   int numVertices = graph.size();
   vector<int> dist(numVertices, INT_MAX);
   vector<bool> visited(numVertices, false);

   dist[source] = 0;
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   pq.push(make_pair(0, source));

   while (!pq.empty()) {
      int u = pq.top().second;
      pq.pop();

      if (visited[u]) {
         continue;
      }

      visited[u] = true;

      for (const Edge& edge : graph[u]) {
         int v = edge.destination;
         int weight = edge.weight;

         if (dist[u] + weight < dist[v]) {
            dist[v] = dist[u] + weight;
            pq.push(make_pair(dist[v], v));
         }
      }
   }

   return dist;
}

int main() {
   int numVertices = 4;
   vector<vector<Edge>> graph(numVertices);

   // Adding edges to the graph
   graph[0].push_back(Edge(1, 2));
   graph[0].push_back(Edge(2, 5));
   graph[1].push_back(Edge(2, 1));
   graph[1].push_back(Edge(3, 7));
   graph[2].push_back(Edge(3, 3));

   int source = 0;
   vector<int> shortestDistances = dijkstra(graph, source);

   cout << "Shortest distances from source vertex " << source << ":\n";
   for (int i = 0; i < numVertices; i++) {
      cout << "Vertex " << i << ": " << shortestDistances[i] << endl;
   }

   return 0;
}

Sortie

Shortest distances from source vertex 0:
Vertex 0: 0
Vertex 1: 2
Vertex 2: 3
Vertex 3: 6

La traduction chinoise de

Explication

est :

Explication

Dans cette approche, nous utilisons une file d'attente prioritaire pour optimiser le processus de recherche de l'arête pondérée minimale pour chaque sous-ensemble. Vous trouverez ci-dessous une explication détaillée du code −

La structure du code et les fonctions d'assistance (telles que find et unionSets) restent les mêmes que la méthode précédente.

La fonction

boruvkaMST est modifiée pour utiliser une file d'attente prioritaire afin de trouver efficacement le bord pondéré minimum pour chaque sous-ensemble.

Au lieu d'utiliser le tableau le moins cher, nous créons maintenant une file d'attente prioritaire (pq) d'arêtes. On l'initialise avec les bords du graphe.

La boucle principale s'exécute jusqu'à ce que numTrees devienne 1, similaire à la méthode précédente.

À chaque itération, nous extrayons le bord de poids minimum (minEdge) de la file d'attente prioritaire.

Ensuite, nous utilisons la fonction find pour trouver le sous-ensemble auquel appartiennent la source et la cible de minEdge.

Si les sous-ensembles sont différents, nous ajoutons minEdge au vecteur selectedEdges, mettons à jour MSTWeight, effectuons une fusion des sous-ensembles et réduisons numTrees.

Le processus continuera jusqu'à ce que tous les composants soient dans un arbre.

Enfin, nous générons les poids MST et les arêtes sélectionnées.

La fonctionnalité principale est la même que la méthode précédente, nous avons des entrées prédéfinies à des fins de tests.

Conclusion

L'algorithme Boruvka fournit une solution efficace pour trouver l'arbre couvrant minimum d'un graphique pondéré. Notre équipe a exploré en profondeur deux voies différentes lors de l'implémentation de l'algorithme en C++ : une approche traditionnelle ou « naïve ». Un autre utilise des files d’attente prioritaires. Cela dépend des exigences spécifiques du problème donné. Chaque méthode présente certains avantages et peut être mise en œuvre en conséquence. En comprenant et en implémentant l'algorithme Boruvka, vous pouvez résoudre efficacement les problèmes d'arbre couvrant minimum dans les projets C++.

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!