一、最小生成树简介：
给定一张边带权的无向图G=（V,E），n=|V|，m=|E|。由 V 中的全部 n 个顶点和 E 中的 n-1 条边构成的无向连通子图被称为G的一棵生成树。边的权值之和最小的生成树被称为无向图G 的最小生成树（MST）。
1。任意一棵最小生成树一定包含无向图中权值最小的边。

2。给定一张无向图G=（V，E）,n=|V|，m=|E|。从E中选出 k < n-1 条边构成G 的一个生成森林。若再从剩余 的 m-k 条边中选 n-1-k 条边添加到生成森林中，使其成为G 的生成树，并且选出的边的边权之和最小，则该生成树一定包含这m-k条边中连接生成森林的两个不连通节点的边权最小的边。

3。最小生成树是树，其边数等于顶点数减1，且树内一定不会有环。

4。对于给定的图，其最小生成树可以不唯一，但其边权之和一定唯一。

5。其根节点可以是这棵树上的任一节点。
一、Kruskal：
边贪心。
1.建立并查集，每个点各自构成一个集合。
2.把所有边按照权值从大到小排序，依次扫描每条边（x，y，z）。
3.若x，y属于同一集合（连通），则忽略这条边，继续扫描下一条。
4.否则，合并x，y集合，并把z累加到答案中。
5.直到最小生成树中的边数等于总顶点数-1，或是测试完所有边时结束。
而当结束时，如果最小生成树的边数小于总顶点数-1，说明该图不连通。
适合处理稀疏图（边少的），时间复杂度为O（mlogm）。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500005;
const int _max=100005;
int f[_max];
struct node
{
    int x;
    int y;
    int z;
}edge[maxn];

void init(int n)
{
    for(int i=1;i<=n;i++)
        f[i]=i;
}

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

bool cmp(node &a,node &b)
{
    return a.z<b.z;
}

int Kruskal(int n,int m)
{
    sort(edge+1,edge+m+1,cmp);
    int num=0;
    int ans=0;

    for(int i=1;i<=m;i++)
    {
        int x=fi(edge[i].x);
        int y=fi(edge[i].y);
        if(x==y) continue;

        f[x]=y;
        num++;
        ans+=edge[i].z;
        if(num==n-1) break;
    }
    if(num<n-1) return -1;
    else return ans;
}

int main(void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    init(n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
    }
    int k=Kruskal(n,m);
    if(k==-1) printf("不连通\n");
    else printf("%d\n",k);

    return 0;
}

二、Prim算法：
点贪心。
prim算法总是维护最小生成树的一部分，最初，prim算法仅确定一号节点属于的最小生成树。
在任意时刻，设已经确定的属于最小生成树的节点的集合为T，生于节点的集合为S。prim算法找到两个端点分别属于集合T,S的权值最小的边，然后把x从S集合中删除，加入到T集合中，并把z累积到答案中。
可以维护数组d，若x∈S，d（x）表示节点x与集合T中的节点之间权值最小的边的边权值；
若x∈T，则d（x）表示x被加入T时选出的最小边的权值。

时间复杂度为O（n*n），可以用二叉堆优化到O（mlogn）。
主要用于稠密图（边多），尤其是完全图的最小生成树。
1.朴素模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500005;
const int _max=100005;
int head[_max],ver[maxn],edge[maxn],nt[maxn];
bool ha[_max];
int d[_max];
int tot;
int n,m;
void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    nt[tot]=head[x],head[x]=tot;
}

void prim(void)
{
    memset(ha,0,sizeof(ha));
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    int ans=0;
    for(int i=1;i<n;i++)//for(int i=1;i<=n;i++) 可以直接累加计算ans
    {
        int x=0;
        for(int j=1;j<=n;j++)
            if(!ha[j]&&(x==0||d[j]<d[x])) x=j;
        ha[x]=true;
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i],z=edge[i];
            if(!ha[y]) d[y]=min(d[y],z);//防止已在集合的点被更新
        }
    }
    return ;
}

int main(void)
{
    memset(head,0,sizeof(head));
    tot=0;
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    prim();
    int ans=0;
    for(int i=2;i<=n;i++)
        ans+=d[i];

    printf("%d\n",ans);
    return 0;
}

2.优先队列优化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
const int maxn=500005;
const int _max=100005;
int head[_max],ver[maxn],edge[maxn],nt[maxn];
bool ha[_max];
int d[_max];
int tot;
int n,m;
void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z;
    nt[tot]=head[x],head[x]=tot;
}

int prim(void)
{
    memset(ha,0,sizeof(ha));
    memset(d,0x3f,sizeof(d));
    d[1]=0;

    priority_queue<pair<int,int> >q;
    q.push(make_pair(0,1));
    int ans=0;
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(ha[x]) continue;
        ans+=d[x];

        ha[x]=true;
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i],z=edge[i];
            if(!ha[y]&&d[y]>z)
            {
                d[y]=z;
                q.push(make_pair(-d[y],y));
            }
        }
    }
    return ans;
}

int main(void)
{
    memset(head,0,sizeof(head));
    tot=0;
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    int k=prim();
    printf("%d\n",k);
    int ans=0;
    for(int i=2;i<=n;i++)
        ans+=d[i];

    printf("%d\n",ans);
    return 0;
}