数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
