Boruvka-Algorithmus in C++ für minimalen Spanning Tree

In der Graphentheorie ist das Finden des Minimum Spanning Tree (MST) eines verbundenen gewichteten Graphen ein häufiges Problem. MST ist eine Teilmenge von Diagrammkanten, die alle Eckpunkte verbindet und das Gesamtkantengewicht minimiert. Ein effizienter Algorithmus zur Lösung dieses Problems ist der Boruvka-Algorithmus.

Grammatik

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

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

Algorithmus

Lassen Sie uns nun die Schritte skizzieren, die zum Finden des minimalen Spannbaums im Boruvka-Algorithmus erforderlich sind −

• Initialisieren Sie MST mit dem leeren Satz.

• Erstellen Sie für jeden Scheitelpunkt eine Teilmenge, wobei jede Teilmenge nur einen Scheitelpunkt enthält.

• Wiederholen Sie die folgenden Schritte, bis der minimale Spannbaum (MST) V-1-Kanten hat (V ist die Anzahl der Eckpunkte im Diagramm) −

  • Finden Sie für jede Teilmenge die günstigste Kante, die sie mit der anderen Teilmenge verbindet.

  • Fügen Sie ausgewählte Kanten zu einem minimalen Spannbaum hinzu.

  • Führen Sie eine Vereinigungsoperation für eine Teilmenge ausgewählter Kanten durch.

• Geben Sie den minimalen Spannbaum aus.

Methode

Im Boruvka-Algorithmus gibt es mehrere Möglichkeiten, die günstigste Kante zu finden, die jede Teilmenge verbindet. Hier sind zwei gängige Methoden −

Methode 1: Einfache Methode

Iterieren Sie für jede Teilmenge alle Kanten und finden Sie die kleinste Kante, die sie mit der anderen Teilmenge verbindet.

Verfolgen Sie ausgewählte Kanten und führen Sie Verbindungsoperationen durch.

Beispiel

#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;
}

Ausgabe

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

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Wir definieren zunächst zwei Strukturen – Edge und Subset. Kante stellt eine Kante im Diagramm dar, einschließlich Quelle, Ziel und Gewicht der Kante. Die Teilmenge stellt eine Teilmenge der Union-Abfragedatenstruktur dar, einschließlich übergeordneter und Ranking-Informationen.

Die Suchfunktion ist eine Hilfsfunktion, die Pfadkomprimierung verwendet, um eine Teilmenge von Elementen zu finden. Es findet rekursiv die Vertreter (übergeordnete Knoten) der Teilmenge, zu der das Element gehört, und komprimiert den Pfad, um zukünftige Abfragen zu optimieren.

Die Funktion

unionSets ist eine weitere Hilfsfunktion, die zwei Teilmengen durch rangweise Zusammenführung zusammenführt. Es findet Vertreter zweier Teilmengen und führt sie basierend auf ihrem Rang zusammen, um einen ausgewogenen Baum zu erhalten.

Die

boruvkaMST-Funktion verwendet als Eingabe einen Kantenvektor und eine Anzahl von Eckpunkten (V). Es implementiert den Boruvka-Algorithmus, um MST zu finden.

Innerhalb der boruvkaMST-Funktion erstellen wir einen Vektor selectedEdges, um die Kanten von MST zu speichern.

Wir erstellen ein Array von Subset-Strukturen zur Darstellung von Subsets und initialisieren sie mit Standardwerten.

Wir erstellen außerdem ein Array günstigstes, um den günstigsten Rand für jede Teilmenge zu verfolgen.

Die Variable numTrees wird auf die Anzahl der Scheitelpunkte initialisiert und MSTWeight wird auf 0 initialisiert.

Der Algorithmus funktioniert durch wiederholtes Kombinieren von Komponenten, bis sich alle Komponenten in einem Baum befinden. Die Hauptschleife läuft, bis numTrees 1 wird.

In jeder Iteration der Hauptschleife iterieren wir über alle Kanten und ermitteln die minimal gewichtete Kante für jede Teilmenge. Wenn eine Kante zwei verschiedene Teilmengen verbindet, aktualisieren wir das günstigste Array mit dem Index der am wenigsten gewichteten Kante.

Als nächstes durchlaufen wir alle Teilmengen. Wenn eine Teilmenge eine Kante mit minimalem Gewicht hat, fügen wir sie dem selectedEdges-Vektor hinzu, aktualisieren MSTWeight, führen die Vereinigungsoperation der Teilmengen durch und reduzieren den Wert von numTrees.

Abschließend geben wir die MST-Gewichte und ausgewählten Kanten aus.

Die Hauptfunktion fordert den Benutzer auf, die Anzahl der Scheitelpunkte und Kanten einzugeben. Dann nimmt es die Eingabe (Quelle, Ziel, Gewicht) für jede Kante und ruft die boruvkaMST-Funktion mit der Eingabe auf.

Methode 2: Prioritätswarteschlange verwenden

Erstellen Sie eine nach Gewicht sortierte Prioritätswarteschlange, um Kanten zu speichern.

Finden Sie für jede Teilmenge die Kante mit minimalem Gewicht, die sie mit einer anderen Teilmenge aus der Prioritätswarteschlange verbindet.

Verfolgen Sie ausgewählte Kanten und führen Sie Verbindungsoperationen durch.

Beispiel

#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;
}

Ausgabe

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

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Bei diesem Ansatz verwenden wir eine Prioritätswarteschlange, um den Prozess zum Finden der minimal gewichteten Kante für jede Teilmenge zu optimieren. Nachfolgend finden Sie eine detaillierte Erklärung des Codes −

Die Codestruktur und Hilfsfunktionen (wie find und unionSets) bleiben dieselben wie bei der vorherigen Methode.

Die

boruvkaMST-Funktion wurde geändert, um eine Prioritätswarteschlange zu verwenden, um die minimal gewichtete Kante für jede Teilmenge effizient zu finden.

Anstatt das günstigste Array zu verwenden, erstellen wir jetzt eine Edge Priority Queue (pq). Wir initialisieren es mit den Kanten des Diagramms.

Die Hauptschleife läuft, bis numTrees 1 wird, ähnlich wie bei der vorherigen Methode.

In jeder Iteration extrahieren wir die Kante mit minimalem Gewicht (minEdge) aus der Prioritätswarteschlange.

Dann verwenden wir die Suchfunktion, um die Teilmenge zu finden, zu der die Quelle und das Ziel von minEdge gehören.

Wenn die Teilmengen unterschiedlich sind, fügen wir minEdge zum selectedEdges-Vektor hinzu, aktualisieren MSTWeight, führen eine Zusammenführung der Teilmengen durch und reduzieren numTrees.

Der Vorgang wird fortgesetzt, bis sich alle Komponenten in einem Baum befinden.

Abschließend geben wir die MST-Gewichte und ausgewählten Kanten aus.

Die Hauptfunktionalität ist die gleiche wie bei der vorherigen Methode, wir haben zu Testzwecken vordefinierte Eingaben.

Fazit

Der Boruvka-Algorithmus bietet eine effiziente Lösung zum Finden des minimalen Spannbaums eines gewichteten Diagramms. Unser Team hat bei der Implementierung des Algorithmus in C++ zwei verschiedene Wege eingehend untersucht: einen traditionellen oder „naiven“ Ansatz. Ein anderer nutzt Prioritätswarteschlangen. Hängt von den spezifischen Anforderungen des jeweiligen Problems ab. Jede Methode hat bestimmte Vorteile und kann entsprechend umgesetzt werden. Durch das Verständnis und die Implementierung des Boruvka-Algorithmus können Sie Minimal-Spanning-Tree-Probleme in C++-Projekten effizient lösen.

Das obige ist der detaillierte Inhalt vonBoruvka-Algorithmus in C++ für minimalen Spanning Tree. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!