最小生成树(模板)

最小生成树两种方法：
Prim和Kruskal

关于时间复杂度：

prim:该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。

kruskal:需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系，可以证明其时间复杂度为O（eloge）。适合稀疏图。

Kruskal讲解

利用并查集来求
连通块：无向图中相互连通 的一些点

具体步骤：将一个连通块当做一个集合，然后按照边的大小（从小到大）进行排序，一开始认为每个点都是孤立的，自身是一个集合。
然后按照顺序枚举每一个边，如果这个边连接了不同的集合，就用并查集将两个集合合并在一起，就成一个集合了。并将这条边加入最小生成树。如果这条边连接的是一个集合，就直接跳过，直到n-1条边为止

Kruskal模板

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int n,m,i,j,u,v,total;
struct edge{
   
    int start,to;long long val;
}bian[2000005];
int f[100000];
long long ans;

int find(int x)//并查集部分
{
   
    if (f[x]==x) return x; 
	else  return find(f[x]);
     
}

bool cmp(edge a,edge b)//结构体快排时用到的
{
   
    return a.val<b.val;	
}

inline void kruskal()//最小生成树
{
   

    for(int i=1;i<=m;i++)
    {
   
        u=find(bian[i].start);
        v=find(bian[i].to);
        if(u==v) continue;//判断在不在同一个并查集里面，在就下一个循环
            ans+=bian[i].val;//不在，就加上
            f[u]=v;//连接两个并查集
            total++;
            if(total==n-1) break;//当形成了最小生成树后，退出（之后做的也没用了）
    }
} 
int main()
{
   
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) f[i]=i;
    for(i=1;i<=m;i++)
    {
   
        scanf("%d%d%d",&bian[i].start,&bian[i].to,&bian[i].val);
    }
    sort(bian+1,bian+m+1,cmp);//快排边长
    kruskal();
    printf("%d",ans);
    return 0;
}

Prim讲解

Prim中白点代表已经进入最小生成树的点，蓝点代表未进入最小生成树的二点
MST表示最小生成树权值
min[v]表示蓝点v与白点相连的最小边权值
Prim算法每次回循环将一个蓝点u变成白点，并且此蓝点与白点相连的最小边权值min[u]还是当前所有蓝点中最小的，这样相当于向生成树中添加了n-1次最小的边，最后的到的肯定是最小生成树
步骤：
（a）初始化：min=inf min[1]=0 MST=0
（b）for枚举点
1.寻找min[u]最小的蓝点u
2.将u标记为白点，说明已经进入最小生成树
3.MST+这条边min[u]
4.for枚举与u相连的蓝点v
if(w[u][v]<min[v])min[v]=w[u][v]
不断更新边权
5.输出答案

Prim模板

#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
il int read()
{
   
    re int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
   if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}//快读，不理解的同学用cin代替即可
#define inf 123456789
#define maxn 5005
#define maxm 200005
struct edge
{
   
    int v,w,next;
}e[maxm<<1];
//注意是无向图，开两倍数组
int head[maxn],dis[maxn],cnt,n,m,tot,now=1,ans;
//已经加入最小生成树的的点到没有加入的点的最短距离，比如说1和2号节点已经加入了最小生成树，那么dis[3]就等于min(1->3,2->3)
bool vis[maxn];
//链式前向星加边
il void add(int u,int v,int w)
{
   
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
//读入数据
il void init()
{
   
    n=read(),m=read();
    for(re int i=1,u,v,w;i<=m;++i)
    {
   
        u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,w);
    }
}
il int prim()
{
   
    //先把dis数组附为极大值
    for(re int i=2;i<=n;++i)
    {
   
        dis[i]=inf;
    }
    //这里要注意重边，所以要用到min
    for(re int i=head[1];i;i=e[i].next)
    {
   
        dis[e[i].v]=min(dis[e[i].v],e[i].w);
    }
    while(++tot<n)//最小生成树边数等于点数-1
    {
   
        re int minn=inf;//把minn置为极大值
        vis[now]=1;//标记点已经走过
        //枚举每一个没有使用的点
        //找出最小值作为新边
        //注意这里不是枚举now点的所有连边，而是1~n
        for(re int i=1;i<=n;++i)
        {
   
            if(!vis[i]&&minn>dis[i])
            {
   
                minn=dis[i];
                now=i;
            }
        }
        ans+=minn;
        //枚举now的所有连边，更新dis数组
        for(re int i=head[now];i;i=e[i].next)
        {
   
            re int v=e[i].v;
            if(dis[v]>e[i].w&&!vis[v])
            {
   
                dis[v]=e[i].w;
            }
        }
    }
    return ans;
}
int main()
{
   
    init();
    printf("%d",prim());
    return 0;
}