定义

• 一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边
• 最小生成树：一个具有n个节点的连通无向图的最小生成树是原图的极小连通子图(所有生成树中权值和最小的)

Prim算法

• Prim算法多用于处理稠密图
• 时间复杂度：$O(n^2)$

基本思路

S为当前已经在连通块中的所有点的集合
1. dist[i] = 0x3f3f3f3f
2. for n 次
    t<-S外离S最近的点
    利用t更新S外点到S的距离
    st[t] = true
n次迭代之后所有点都已加入到S中

Prim算法和Dijkstra算法长得很像，需要对比学习
联系：Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离

代码模板

无向图g的初始化需要g[a][b] = g[b][a], g[a][a]=0, 没有边需要置为INF
st数组表示是否被加入到集合中
dist数组表示顶点到集合的距离

int prim(){
    Arrays.fill(dist, 0x3f3f3f3f);
    int res = 0;

    for(int i = 0; i < n; i++){
        //找出所有没有被添加到集合中，且距离集合最近的点
        int t = -1;
        for(int j = 1; j <= n; j++){
            if(!st[j] && (t == -1 || dist[t] > dist[j])){
                t = j;
            }
        }
        //除了第一个点之外，没有其他点可以添加进集合，说明没有连通块
        if(i > 0 && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
        if(i > 0) res += dist[t];
        st[t] = true;

        //这个循环一定要放最后，否则出现自环负边的时候，会把自己更新了
        for(int j = 1; j <= n; j++){
            dist[j] = Math.min(dist[j], g[t][j]);
        }
    }
    //res为INF代表图不连通，否则输出res
    return res;
}

Kruskal算法

• Kruskal算法用于处理稀疏图
• 时间复杂度： $O(mlogm)$

基本思路

1.将所有边按权重从小到大排序 O(mlogm) 多用快排，这是Kruskal的瓶颈
2.枚举所有边a,b,权重为c
    if(a.b不连通){
        将a,b加入集合中，并统计权值和与集合内的边数
    }

第二步为并查集的操作，这一步总时间负责度为O(m)
需要使用一个cnt变量记录加入集合的边数，如果cnt = n-1表示图是连通的，否则图不连通，没有最小生成树

代码模板

//Kruskal不需要建图，只要保存所有边即可
class Edge{
    int a;
    int b;
    int w;
    public Edge(int a, int b, int w){
        this.a = a;
        this.b = b;
        this.w = w;
    }
}

//并查集
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void union(int x, int y){
    p[find(y)] = find(x);
}

int kruskal(){
    //按权重排序
    Arrays.sort(edges, (o1,o2) -> o1.w-o2.w);
    int res = 0, cnt = 0;
    for(int i = 0; i < m; i++){
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if(find(a) != find(b)){
            union(a,b);
            res += w;
            cnt++;
        }
    }
    // cnt == n-1表示有最小生成树，否则没有
    return cnt == n-1 ? res : -1;
}