C++中的Boruvka演算法用於最小生成樹

在圖論中，尋找連通加權圖的最小生成樹（MST）是一個常見的問題。 MST是圖的邊的子集，它連接了所有的頂點並最小化了總邊權。解決這個問題的一個高效率演算法是Boruvka演算法。

文法

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

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

演算法

現在，讓我們概述Boruvka演算法中涉及的尋找最小生成樹的步驟−

• 將 MST 初始化為空集。

• 為每個頂點建立一個子集，其中每個子集只包含一個頂點。

• 重複以下步驟，直到最小生成樹(MST)有V-1條邊（V是圖中頂點的數量）−

  • 對於每個子集，找到將其連接到另一個子集的最便宜的邊。

  • 將選定的邊加入到最小生成樹。

  • 對所選邊的子集執行並集操作。

• 輸出最小生成樹。

方法

在Boruvka演算法中，有多種方法可以找到連接每個子集的最便宜的邊。以下是兩種常見的方法−

方法一：樸素方法

對於每個子集，遍歷所有邊，並找到將其連接到另一個子集的最小邊。

追蹤選定的邊並執行聯合操作。

範例

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

輸出

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

Explanation

的中文翻譯為：

解釋

我們先定義兩個結構 - Edge 和 Subset。 Edge 表示圖中的一邊，包含邊的來源、目的地和權重。 Subset表示並檢查資料結構的子集，包含父級和排名資訊。

find函數是一個輔助函數，它使用路徑壓縮來尋找元素的子集。它遞歸地查找元素所屬的子集的代表（父節點），並壓縮路徑以優化未來的查詢。

unionSets函數是另一個輔助函數，使用按秩合併的方式對兩個子集進行合併。它找到兩個子集的代表，並根據秩進行合併，以保持平衡樹。

boruvkaMST 函數採用邊向量和頂點數 (V) 作為輸入。它實作了 Boruvka 演算法來查找 MST。

在 boruvkaMST 函數內，我們建立一個向量 selectedEdges 來儲存 MST 的邊。

我們建立一個Subset結構的陣列來表示子集，並用預設值初始化它們。

我們也建立了一個陣列 cheapest 來追蹤每個子集的最便宜的邊。

變數 numTrees 被初始化為頂點的數量，MSTWeight 被初始化為 0。

該演算法透過重複組合組件來進行，直到所有組件都在一棵樹中。主循環運行直到 numTrees 變為 1。

在主循環的每次迭代中，我們迭代所有邊並找到每個子集的最小加權邊。如果邊連接兩個不同的子集，我們用最小加權邊的索引來更新最便宜的陣列。

接下來，我們遍歷所有的子集，如果一個子集存在最小權重的邊，我們將其添加到selectedEdges向量中，更新MSTWeight，執行子集的並集操作，並減少numTrees的值。

最後，我們輸出 MST 權重和選定的邊。

主要功能提示使用者輸入頂點數和邊數。然後，它會取得每條邊的輸入（來源、目標、權重）並使用輸入呼叫 boruvkaMST 函數。

方法二：使用優先隊列

建立一個依照權重排序的優先權佇列來儲存邊。

對於每個子集，從優先權佇列中找到將其連接到另一個子集的最小權重邊。

追蹤選定的邊並執行聯合操作。

範例

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

輸出

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

Explanation

的中文翻譯為：

解釋

在這個方法中，我們使用優先權佇列來最佳化尋找每個子集的最小加權邊的過程。下面是程式碼的詳細解釋 −

程式碼結構和輔助函數（如find和unionSets）與先前的方法保持相同。

boruvkaMST 函數被修改為使用優先權佇列來有效地找到每個子集的最小加權邊。

而不是使用最便宜的數組，我們現在創建一個邊的優先隊列（pq）。我們用圖的邊來初始化它。

主循環運行直到 numTrees 變成 1，與先前的方法類似。

在每次迭代中，我們從優先隊列中提取最小權重的邊（minEdge）。

然後我們使用find函數找到minEdge的來源和目標所屬的子集。

如果子集不同，我們將minEdge加入到selectedEdges向量中，更新MSTWeight，執行子集的合併，並減少numTrees。

這個過程將繼續，直到所有組件都在一棵樹中。

最後，我們輸出 MST 權重和選定的邊。

主要功能與先前的方法相同，我們有預先定義的輸入用於測試目的。

結論

Boruvka 演算法為尋找加權圖的最小生成樹提供了一個有效的解決方案。在用 C 實作演算法時，我們的團隊深入探索了兩種不同的路徑：一種是傳統的或「樸素」的方法。另一個利用優先權隊列。取決於當前給定問題的具體要求。每種方法都有一定的優點，可以相應地實施。透過理解和實作 Boruvka 演算法，您可以有效地解決 C 專案中的最小生成樹問題。

以上是C++中的Boruvka演算法用於最小生成樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！