破圈法实现最小生成树c++

破圈法（Kruskal's Algorithm），也称为普里姆算法，是一种用于求解无向图中最小生成树的经典算法。在C++中，你可以通过以下步骤实现：

1. **初始化**：创建一个集合（或并查集）来存储所有的顶点，并假设它们都是孤立的。

2. **排序边**：将图的所有边按照权重从小到大排序。

3. **遍历边**：对于每条边，如果它的两个端点不在同一个集合中（即它们还没有形成连通分量），就将这条边加入最小生成树，并合并这两个顶点所在的集合。

4. **重复直到**：所有边都被检查过或者当前集合包含n-1个元素，因为一棵树有n-1条边。

5. **返回结果**：最后剩下的连通分量就是最小生成树。

下面是C++代码的一个简单示例：

#include <iostream>
#include <vector>
#include <set>

using namespace std;

class DisjointSet {
public:
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) parent[x] = y;
    }

private:
    vector<int> parent;
};

int kruskalMST(vector<pair<int, pair<int, int>>> edges) {
    DisjointSet ds(edges.size());
    sort(edges.begin(), edges.end());

    vector<int> mstCost(0);
    for (auto edge : edges) {
        int u = edge.second.first;
        int v = edge.second.second;
        int w = edge.first;

        if (ds.find(u) != ds.find(v)) {
            mstCost.push_back(w);
            ds.unite(u, v);
        }
    }
    return accumulate(mstCost.begin(), mstCost.end(), 0);
}

int main() {
    // 测试数据
    vector<pair<int, pair<int, int>>> edges = {{1, {0, 1}}, {2, {0, 2}}, {3, {1, 3}}, {4, {2, 4}}, {5, {3, 5}}};
    cout << "Minimum spanning tree cost: " << kruskalMST(edges) << endl;
    return 0;
}