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算法中，有多种方法可以找到连接每个子集的最便宜的边。以下是两种常见的方法−

方法一：朴素方法

对于每个子集，遍历所有边，并找到将其连接到另一个子集的最小边。

跟踪选定的边并执行联合操作。

示例

#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