資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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 是圖中頂點的數量） -
對於每個子集，找到連線它到另一個子集的最便宜的邊。
將選定的邊新增到 MST 中。
對選定邊的子集執行並集操作。
輸出 MST。
方法
在 Boruvka 演算法中，有多種方法可以找到連線每個子集的最便宜的邊。以下兩種方法很常見 -
方法 1：樸素方法
對於每個子集，遍歷所有邊並找到連線它到另一個子集的最小邊。
跟蹤選定的邊並執行並集操作。
示例
#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 表示用於並查集資料結構的子集，包含父節點和秩資訊。
find 函式是一個輔助函式，它使用路徑壓縮來查詢元素的子集。它遞迴地找到元素所屬的子集的代表（父節點），並壓縮路徑以最佳化將來的查詢。
unionSets 函式是另一個輔助函式，它使用按秩合併執行兩個子集的並集。它找到兩個子集的代表，並根據秩執行並集以維護平衡樹。
boruvkaMST 函式以邊向量和頂點數 (V) 作為輸入。它實現 Boruvka 演算法來查詢 MST。
在 boruvkaMST 函式內部，我們建立一個 selectedEdges 向量來儲存 MST 的邊。
我們建立一個 Subset 結構陣列來表示子集，並使用預設值初始化它們。
我們還建立一個 cheapest 陣列來跟蹤每個子集的最便宜的邊。
變數 numTrees 初始化為頂點數，MSTWeight 初始化為 0。
該演算法透過重複組合元件直到所有元件都在一棵樹中來進行。主迴圈執行直到 numTrees 變成 1。
在主迴圈的每次迭代中，我們遍歷所有邊併為每個子集找到最小權重的邊。如果邊連線兩個不同的子集，我們使用最小權重邊的索引更新 cheapest 陣列。
接下來，我們遍歷所有子集，如果子集存在最小權重邊，我們將它新增到 selectedEdges 向量中，更新 MSTWeight，執行子集的並集，並遞減 numTrees。
最後，我們輸出 MST 權重和選定的邊。
主函式提示使用者輸入頂點數和邊數。然後它為每條邊（源、目標、權重）獲取輸入，並使用輸入呼叫 boruvkaMST 函式。
方法 2：使用優先佇列
建立一個優先佇列來儲存按權重排序的邊。
對於每個子集，從優先佇列中找到連線它到另一個子集的最小權重邊。
跟蹤選定的邊並執行並集操作。
示例
#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 函式被修改為使用優先佇列來有效地為每個子集找到最小權重邊。
我們不再使用 cheapest 陣列，而是建立了一個邊的優先佇列 (pq)。我們用圖的邊初始化它。
主迴圈執行直到 numTrees 變成 1，與之前的方法類似。
在每次迭代中，我們從優先佇列中提取最小權重邊 (minEdge)。
然後，我們使用 find 函式找到 minEdge 的源和目標所屬的子集。
如果子集不同，我們將 minEdge 新增到 selectedEdges 向量中，更新 MSTWeight，執行子集的並集，並遞減 numTrees。
該過程持續進行，直到所有元件都在一棵樹中。
最後，我們輸出 MST 權重和選定的邊。
主函式與之前的方法相同，我們在其中預定義了用於測試的輸入。
結論
Boruvka 演算法為查詢加權圖的最小生成樹提供了一種有效的解決方案。我們的團隊在用 C++ 實現該演算法時深入探索了兩條不同的路徑：一種是傳統方法或“樸素”方法。另一種利用優先佇列。根據手頭給定問題的具體要求。每種方法都具有一定的優勢，可以相應地實施。透過理解和實現 Boruvka 演算法，您可以在 C++ 專案中有效地解決最小生成樹問題。
511 次瀏覽
