最小生成树

4.最小生成树

最小生成树：由n个节点，和n-1条边构成的无向连通图被称为G的一颗生成树，在G的所有生成树中，边的权值之和最小的生成树，被称为G的最小生成树。(换句话说就是用最小的代价把n个点都连起来)

Prim算法（普利姆）
- 朴素版Prim（时间复杂度O(n^2)，适用于稠密图）
- 堆优化版Prim（时间复杂度O(mlogn)，适用于稀疏图）基本不用
Kruskal算法（克鲁斯卡尔）适用于稀疏图，时间复杂度O(mlogm)

如果是稠密图，通常选用朴素版Prim算法，因为其思路比较简洁，代码比较短，如果是稀疏图，通常选用Kruskal算法，因为其思路比Prim简单清晰。堆优化版的Prim通常不怎么用。

（一）Prim

朴素Prim

与朴素dijkstra思想几乎一样，只不过Prim算法的距离指的是点到最小生成树的集合的距离，而dijkstra算法的距离是点到起点的距离。适用于稠密图

**实现思路：**和朴素Dijkstra很像

初始化各点到集合的距离为INF
n次循环，每次找到集合外且距离集合最近的点t，需要先判断除第一个点外找到的距离最近的点t距离是不是INF
- 若是则不存在最小生成树了，结束；否则可能还存在，继续操作，用该点t来更新其他点到集合的距离（这里就是和Dijkstra最主要的区别），然后将该点t加入集合
关于到集合的距离最近的点：实际上就是不在集合中的点与集合内的点的各个距离中的最小值，每次加入新的点都会尝试更新一遍

dist[j]=min(dist[j]，g[t][j])（在Dijkstra中是dist[j]=min(dist[j]，dist[t]+g[t][j])）

AcWing 858. Prim算法求最小生成树

注意：本题由于未设起点所以要迭代n次，并且图中可能存在负的自环，因此计算最小生成树的总距离要在更新各点到集合距离之前。且该图为无向图，含重边，则构建边要注意

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
int g[N][N],dist[N];
bool st[N];
int n,m;
 
//返回最小生成树权重之和
int prim(){
    memset(dist,0x3f,sizeof dist);
    int res=0;//记录结果
    
    for(int i=0;i<n;i++ ){//i从0开始 1开始无所谓
        int t=-1;
        
        //找到当前的集合外距离集合最近的点
        for(int j=1;j<=n;j++)
            if(!st[j] && (t==-1 || dist[t]>dist[j])) t=j;
        
        //判断该点不是第一个点 且到集合距离为INF
        if(i && dist[t]=INF) return INF; //不存在最小生成树
        if(i) res+=dist[t];
        
        //更新距离
        for(int j=1;i<=n;j++){
            dist[j]=min(dist[j],g[t][j]);
        }
        st[t]=true;//标记进入集合
    }
    return res;
}
 
int mian(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int t=prim();
 
    if(t==INF) puts("impossible");
    else cout<<t;
    return 0;
 
}

堆优化Prim

思路和堆优化的Dijkstra思路基本一样，且基本不用，对于稀疏图，不如用Kruskal，这里略过

（二）Kruskal

适用于稀疏图，时间复杂度O(mlogm)

先将所有边按照权重，从小到大排序（快排，使用sort函数） O(mlogn)
从小到大枚举每条边(a，b，w)，若a，b不连通，则将这条边，加入集合中（将a点和b点连接起来） 实质上并查集的一个应用（两点之间加边、看两点是否在一个连通块），时间复杂度为O(m)

无需邻接表/邻接矩阵存储图，直接使用结构体，表示边及其权值

AcWing 859. Kruskal算法求最小生成树

实现思路：借助并查集

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200010;
int p[N];//父节点数组
int n,m;
struct Edge{
    int a,b,w;
    //重载一下 使用sort函数时按照w的值排序
    bool operator <(const Edge &W)const{
        return w < W.w;
    }
}edge[N];
 
//并查集：找集合根结点
int find(int x){
    if(p[x]!=x) return p[x]=find(p[x]);
}
 
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,w;
        cin>>a>>b>>w;
        edge[i]={a,b,w};
    }
    
    sort(edge,edge+m);//按照边的权值排序
    for(int i=1;i<=n;i++) p[i]=i;//并查集初始化各个结点
    
    int res=0,cnt=0;//res存储最小生成树权值之和 cnt生成树边数 判断是否存在最小生成树
    
    //遍历所有边
    for(int i=0;i<m;i++){
        int a=edge[i].a,b=edge[i].b,w=edge[i].w;
        //找到两点各自的根结点 用于判断两点是否连通
        a=find[a],b=find[b];
        if(a!=b){//两点不连通 要使其连通
            p[a]=b;//并查集的合并
            res+=w;//累计权值
            cnt++;//边数++
        }
    }
    if(cnt<n-1) puts("impossible");//无最小生成树
    else cout<<res;
    return 0;
}

编程笔记

探索