在图论中，寻找连通加权图的最小生成树（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
#include
#include
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[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& edges, int V) {
std::vector 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 1) {
for (int i = 0; i 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
