极客笔记C++ Boruvka算法求最小生成树
在图论中，求解连通带权图的最小生成树（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。Edge代表图中的一条边，包含边的起点、终点和权重。Subset代表用于并查集数据结构的子集，包含父节点和秩的信息。
find函数是一个辅助函数，它使用路径压缩来找到一个元素所属的子集。它递归地找到子集的代表元素（父节点），并压缩路径以优化未来的查询。
unionSets函数是另一个辅助函数，它使用按秩合并的方法将两个子集进行合并。它找到两个子集的代表元素，并根据秩进行合并，以保持平衡树。
boruvkaMST函数接受一组边和顶点数（V）作为输入。它实现了Boruvka算法来找到最小生成树。
在boruvkaMST函数内部，我们创建一个vector selectedEdges来存储最小生成树的边。
我们创建一个Subset结构的数组来表示子集，并用默认值初始化它们。
我们还创建一个cheapest数组来跟踪每个子集的最便宜的边。
变量numTrees被初始化为顶点数，并且MSTWeight被初始化为0。
该算法通过不断组合组件直到所有组件都在一棵树中来进行。主循环运行直到numTrees变为1。
在主循环的每次迭代中，我们遍历所有的边，对于每个子集找到权重最小的边。如果这条边连接了两个不同的子集，我们使用最小权重边的索引更新cheapest数组。
接下来，我们遍历所有的子集，如果一个子集存在最小权重边，我们将其添加到selectedEdges向量中，更新MSTWeight，进行子集的并操作，并将numTrees减1。
最后，我们输出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函数被修改为使用一个优先队列来高效地找到每个子集的最小带权边。
我们现在创建一个边的优先队列（pq）而不是使用cheapest数组。我们用图的边初始化它。
主循环运行直到numTrees变为1，与之前的方法类似。
在每次迭代中，我们从优先队列中提取最小带权边（minEdge）。
然后我们使用find函数找到minEdge的源和目的地所属的子集。
如果子集不同，我们将minEdge添加到selectedEdges向量中，更新MSTWeight，执行子集的union操作，并将numTrees减一。
该过程继续，直到所有组件都在一个树中。
最后，我们输出MST的权重和所选的边。
main函数与之前的方法相同，我们为测试目的预定义了输入。
结论
Boruvka的算法为找到加权图的最小生成树提供了高效的解决方案。在实现这个算法的C++版本时，我们团队探索了两条不同的路径：一种是传统或“朴素”方法，另一种是使用优先队列。根据具体的问题需求，每种方法都有其优势，并可以相应地进行实现。通过理解和实现Boruvka的算法，您可以在C++项目中有效地解决最小生成树问题。