最小生成树的概念：一个用n-1条边连接的树，且所有点到其他点的路径唯一的一条路径叫做最小生成树。

Kruskal算法

Kruskal算法是用来求解最小生成树问题的算法之一。

Kruskal算法从边出发，利用贪心的思想，先使用快速排序算法进行预处理排序，之后选择边权最小邻边。

Kruskal 算法是能够在O(mlogm)的时间内得到一个最小生成树的算法。

① 将边按照边权从小到大排序，并建立一个没有边的图T。

② 选出一条没有被选过的边权最小的边。

③ 如果这条边两个顶点在T 中所在的连通块不相同，那么将 它加入图T， 相同就跳过。

④ 重复②和③直到图T 连通为止。

由于只需要维护连通性，可以不需要真正建立图T，可以用并查集 来维护。

算法虽简单，但需要相应的数据结构来支持……具体来说，维护一个森林，查询两个结点是否在同一棵树中，连接两棵树。

抽象一点地说，维护一堆 集合，查询两个元素是否属于同一集合，合并两个集合。

其中，查询两点是否连通和连接两点可以使用并查集维护。

主体代码

void Kruskal(){
    sort(edge,edge + m,cmp);//排序是关键，自带时间复杂度
    for(int i = 0;i < m;i++){//枚举所有节点
        int fx = find(edge[i].x);
        int fy = find(edge[i].y);
        if(fx == fy)continue;
        ans += edge[i].z;
        f[fx] = fy;//路径压缩
        cnt++;
        if(cnt == n - 1)break; //连通图具有n - 1条边
    }
}

并查集部分

int find(int x){
    if(x != f[x])
        return f[x] = find(f[x]);
    return f[x];
}

Prim算法

Prim 算法是另一种常见并且好写的最小生成树算法。该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。

struct point{
    int x,y,l;
}edge[MAXN];

void Prim(){
    int pos;
    dis[0] = 0;
    for(int i = 0;i < n;i++){
        double min = 1e8;
        for(int j = 0;j < n;j++){
            if(!vis[j] && dis[j] < min){
                min = dis[j];
                pos = j;
            }
        }
        ans += min;
        vis[pos] = true;
        for(int j= 0;j < n;j++){
            if(vis[j] == 0 && edge[j].l < dis[j]){
                dis[j] = edge[j].l;
            }
        }
    }
}

算法异同

Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。Prim是以更新过的节点的连边找最小值，Kruskal是直接将边排序。
两者其实都是运用贪心的思路

本篇作为2022CCF赛前复习