在圖論中，尋找連通加權圖的最小生成樹（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
我們先定義兩個結構 - 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
在這個方法中，我們使用優先權佇列來最佳化尋找每個子集的最小加權邊的過程。下面是程式碼的詳細解釋 −
程式碼結構和輔助函數（如find和unionSets）與先前的方法保持相同。
boruvkaMST 函數被修改為使用優先權佇列來有效地找到每個子集的最小加權邊。
而不是使用最便宜的數組，我們現在創建一個邊的優先隊列（pq）。我們用圖的邊來初始化它。
主循環運行直到 numTrees 變成 1，與先前的方法類似。
在每次迭代中，我們從優先隊列中提取最小權重的邊（minEdge）。
然後我們使用find函數找到minEdge的來源和目標所屬的子集。
如果子集不同，我們將minEdge加入到selectedEdges向量中，更新MSTWeight，執行子集的合併，並減少numTrees。
這個過程將繼續，直到所有組件都在一棵樹中。
最後，我們輸出 MST 權重和選定的邊。
主要功能與先前的方法相同，我們有預先定義的輸入用於測試目的。
Boruvka 演算法為尋找加權圖的最小生成樹提供了一個有效的解決方案。在用 C 實作演算法時，我們的團隊深入探索了兩種不同的路徑：一種是傳統的或「樸素」的方法。另一個利用優先權隊列。取決於當前給定問題的具體要求。每種方法都有一定的優點，可以相應地實施。透過理解和實作 Boruvka 演算法，您可以有效地解決 C 專案中的最小生成樹問題。
以上是C++中的Boruvka演算法用於最小生成樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！
