在此前的讨论中，我们已经涉及了关于最小生成树的以下几个主题：
在本文中，我们将探讨 Boruvka 算法。与 Prim 算法和 Kruskal 算法一样，Boruvka 算法也是一种贪心算法。下面是该算法的完整步骤。
1) 输入是一个连通的、带权的无向图。
2) 初始化所有顶点，将每个顶点视为一个单独的分量（或集合）。
3) 将最小生成树（MST）初始化为空。
4) 只要存在多于一个的分量，就对每个分量执行以下操作：
a) 找到一条权值最小的边，该边将此分量连接到任意其他分量。
b) 如果这条最近的边尚未添加，则将其加入 MST。
5) 返回 MST。
以下是上述算法背后的核心思想（这与 Prim 最小生成树算法 的思想是一致的）。
生成树意味着所有顶点必须是连通的。因此，必须将上述提到的两个不相交的顶点子集连接起来，才能形成一个生成树。并且，它们必须通过权值最小的边相连，这样才能构成最小生成树。
让我们通过下面的例子来理解这个算法。
最初，MST 为空。每个顶点都是一个单独的分量，在下图中以蓝色高亮显示。
对于每个分量，找到将其连接到其他某个分量的最廉价的边。
**分量 连接到其他分量的最廉价边**
{0} 0-1
{1} 0-1
{2} 2-8
{3} 2-3
{4} 3-4
{5} 5-6
{6} 6-7
{7} 6-7
{8} 2-8
最廉价的边以绿色高亮显示。此时 MST 变为 {0-1, 2-8, 2-3, 3-4, 5-6, 6-7}。
经过上述步骤后，分量为 {{0,1}, {2,3,4,8}, {5,6,7}}。这些分量用蓝色圆圈圈出。
我们再次重复该步骤，即对于每个分量，找到将其连接到其他某个分量的最廉价的边。
**分量 连接到其他分量的最廉价边**
{0,1} 1-2 (或 0-7)
{2,3,4,8} 2-5
{5,6,7} 2-5
最廉价的边以绿色高亮显示。现在 MST 变为 {0-1, 2-8, 2-3, 3-4, 5-6, 6-7, 1-2, 2-5}
在此阶段，只剩下一个分量 {0, 1, 2, 3, 4, 5, 6, 7, 8}，它包含了所有边。由于只剩下一个分量，我们停止并返回 MST。
实现：
以下是上述算法的实现。输入图表示为边的集合，并使用并查集数据结构来跟踪分量。
C++
“`
// Boruvka‘s algorithm to find Minimum Spanning
// Tree of a given connected, undirected and weighted graph
#include
using namespace std;
// Class to represent a graph
class Graph {
int V; // No. of vertices
vector<vector >graph; // default dictionary to store graph
// A utility function to find set of an element i
// (uses path compression technique)
int find(vector& parent, int i)
{
if (parent[i] == i) {
return i;
}
return find(parent, parent[i]);
}
// A function that does union of two sets of x and y
// (uses union by rank)
void unionSet(vector& parent, vector& rank,
int x, int y)
{
int xroot = find(parent, x);
int yroot = find(parent, y);
// Attach smaller rank tree under root of high rank
// tree (Union by Rank)
if (rank[xroot] < rank[yroot]) {
parent[xroot] = yroot;
}
else if (rank[xroot] > rank[yroot]) {
parent[yroot] = xroot;
}
// If ranks are same, then make one as root and
// increment its rank by one
else {
parent[yroot] = xr