最小生成树kruskal算法并查集

### Kruskal算法通过并查集实现最小生成树

#### 算法概述
Kruskal算法用于寻找带权连通无向图中的最小生成树(Minimum Spanning Tree, MST)[^1]。该方法的核心在于按边的权重升序处理每条边，并利用并查集(Union-Find Set)高效地判断新增加的一条边是否会形成环路。

#### 数据结构定义
为了有效地执行上述逻辑，通常会定义如下数据结构：

- **Edge** 结构体表示一条边及其两端顶点编号以及这条边上的权重；
- **DisjointSet (或 UnionFind)** 类用来维护各个节点所属集合的信息，支持快速查找与合并操作；

struct Edge {
    int u;     // 边的一个端点
    int v;     // 边的另一个端点
    int weight;// 权重
};

class DisjointSet {
private:
    vector<int> parent;
public:
    DisjointSet(int n);
    void unionSets(int a, int b);        // 合并两个子集
    int findParent(int i);               // 查找根结点
};

#### 主要函数说明
接下来展示完整的`kruskalMST()` 函数，它接收一个由若干 `Edge` 组成的列表作为输入参数，并返回构成最小生成树的所有选定边组成的数组:

vector<Edge> kruskalMST(vector<Edge>& edges, int V){
    sort(edges.begin(), edges.end(), [](const auto& e1, const auto& e2){return e1.weight < e2.weight;} ); 

    DisjointSet ds(V);

    vector<Edge> mstEdges;

    for(auto &edge : edges){
        int set_u = ds.findParent(edge.u), set_v = ds.findParent(edge.v);
        
        if(set_u != set_v){
            mstEdges.push_back(edge);
            ds.unionSets(set_u,set_v);
            
            if(mstEdges.size() == V - 1)// 当前已选够V-1条边，则结束循环
                break;
        }
    }

    return mstEdges;
}

此段代码实现了基于贪心策略的选择过程，在每次迭代中选取当前未被加入到MST中最短的一条边[^2]。同时借助于并查集的操作来防止出现回路的情况发生。