Kruskal求最小生成树

### Kruskal算法简介

Kruskal算法是一种用于寻找加权无向图中最小生成树的有效算法。此算法的核心在于按权重升序选择边，并利用并查集检测所选边是否会形成环路，从而逐步构建最小生成树[^1]。

### 算法流程描述

对于给定的一个连通图G=(V,E)，其中V表示顶点集合而E代表边的集合：

- 将所有的边按照其权重从小到大排序；
- 初始化一个空的结果列表用来保存最终形成的最小生成树MST；
- 对于每一个未处理过的边(u,v,w)，如果加入这条边不会造成循环，则将其添加至MST中；这里w指的是u和v之间的距离或成本；
- 当所有可能被考虑进去而不引起闭环现象的边都已经被考察完毕之后停止操作，此时获得的就是原图的一棵最小生成树[^2]。

### C++代码实例展示

下面给出一段基于上述原理编写的C++版本Kruskal算法实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int src, dest, weight;
};

class DisjointSet {
private:
    vector<int> parent, rank;
public:
    DisjointSet(int n);
    void Union(int x, int y);
    int Find(int x);
};

DisjointSet::DisjointSet(int size):parent(size),rank(size){
    for (int i=0;i<size;++i){
        parent[i]=i;
        rank[i]=0;
    }
}

void DisjointSet::Union(int x,int y){
    int rootX = Find(x);
    int rootY = Find(y);

    if(rootX != rootY){
        if(rank[rootX]>rank[rootY]){
            parent[rootY]=rootX;
        }else{
            parent[rootX]=rootY;
            if(rank[rootX]==rank[rootY]) ++rank[rootY];
        }
    }
}

int DisjointSet::Find(int x){
    if(parent[x]!=x){
        parent[x]=Find(parent[x]);
    }
    return parent[x];
}

bool compare(Edge a, Edge b) {return a.weight<b.weight;}

// Function to construct MST using Kruskal's algorithm
pair<vector<Edge>, int> kruskalMST(vector<Edge>& edges, int V) {
    sort(edges.begin(),edges.end(),compare); // Sort all the edges based on their weights
    
    DisjointSet ds(V);
    
    vector<Edge> mstEdges;
    int totalWeight = 0;
    
    for(auto& edge : edges){
        int set_u = ds.Find(edge.src);
        int set_v = ds.Find(edge.dest);
        
        if(set_u!=set_v){ // If including this edge does not form cycle then include it in result and union two sets of vertices.
            mstEdges.push_back({edge});
            ds.Union(set_u,set_v);
            totalWeight+=edge.weight;
            
            if(mstEdges.size()==V-1)// Once we have included V-1 edges break out from loop as now our graph is fully connected with minimum cost possible.
                break;
        }
    }

    return make_pair(mstEdges,totalWeight);
}

这段程序实现了完整的Kruskal算法逻辑，能够接收一组带权边作为输入参数，并返回由这些边组成的最小生成树以及对应的总重量[^3]。