一、最小生成树概念

生成树: 一个连通图的生成树是指一个连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边,一棵有n个顶点的生成树有且仅有n-1条边,如果生成树中再添加一条边，则必定成环.
最小生成树: 在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树.（最小生成树可能不唯一）.
构成最小生成树的准则:
1.必须只使用该网络中的边来构造最小生成树;
2.必须使用有且仅使用n-1条边来连接网络中的n个顶点;
3.不能使用产生回路的边.

最小生成树

二、最小生成树的求法

1、克鲁斯卡尔(Kruskal)算法（稀疏图）

该算法可以称为加边法,初始化最小生成树边数为0,每迭代一次选择一条满足条件的最小代价边,加入到最小生成树的边集合中.

1. 把图中的所有边按代价从小到大排序;
2. 把图中的n个顶点看成独立的n棵树组成的森林;
3. 按权值从小到大选择边,所选的边连接的两个顶点u ,v属于两棵不同的树,使之成为最小生成树的一条边,并将这两棵树合并作为一棵树
4. 重复(3),直到所有顶点都在同一棵树上或者有n-1条边为止.
   
   
   Kruskal算法 > 例：poj1258

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define ll long long
#define ull unsigned long long
#define Max(x, y) (x > y ? x : y)
#define fi(front,end) for (int i = front; i < end; i++)
#define fj(front,end) for (int j = front; j < end; j++)
#define N 105
int fa[N];
struct A{
    int qishi;
    int end;
    int w;
}str[N*N];
bool cmp (A x, A y)
{
    return x.w < y.w;
}
int Find(int x)
{
    if (fa[x] != x)
        fa[x] = Find(fa[x]);
    return fa[x];
}
int main()
{
    ll n, m = 0, ans = 0;
    while (cin >> n)
    {
        m = 0, ans = 0;
    memset(fa,0,sizeof(fa));
    memset(str,0,sizeof(str));
    fi(0,n*2+5)
        fa[i] = i;
    fi(1,n+1)
    {
        fj(1,n+1)
        {
            int a = 0;
            cin >> a;
            str[m].qishi = j;
            str[m].end = i;
            str[m].w = a;
            m++;
        }
    }
    sort(str,str+m,cmp);
    fi(0,m)
    {
        int x1 = Find(str[i].qishi), y1 = Find(str[i].end);
        if (x1 != y1)
        {
            fa[x1] = y1;
            ans += str[i].w;
        }
    }
    cout << ans << endl;
    }
    return 0;
}

普利姆(prim)算法（稠密图）
该算法可以称为加点法,每次迭代选择代价最小的边对应的点,将满足条件的加入到最小生成树中.算法从某个顶点S出发,逐渐覆盖整个连通网的所有顶点.

#include <iostream>
#include <cstring>
#include <algorithm>

#define MAXN 5010
#define MAXM 400010//由于是无向图,开两倍的空间存边
using namespace std;

const int inf=0x3f3f3f3f;
int n,m;
int dis[MAXN],vis[MAXN];
int head[MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;

void add(int a,int b,int c){
    ed[idx]=b;
    val[idx]=c;
    nex[idx]=head[a];
    head[a]=idx++;
}

int prim(){
    for(int i=1;i<=n;i++)//将每个点到生成树的距离初始化为无穷大
        dis[i]=inf;
    int res=0;
    dis[1]=0;//将1(也可选择其他的点)作为生成树的起点
    for(int i=1;i<=n;i++){
        int pos=-1;
        for(int j=1;j<=n;j++)//找到未被访问并且距离最小的点
            if(vis[j]==0&&(pos==-1||dis[pos]>dis[j]))
                pos=j;
        if(dis[pos]==inf)//所有点都未连通
            return -1;
        vis[pos]=1;//标记作为它已被使用
        res+=dis[pos];
        for(int j=head[pos];j!=-1;j=nex[j])//枚举从pos点出发的边并更新dis
            if(vis[ed[j]]==0&&dis[ed[j]]>val[j])
                dis[ed[j]]=val[j];
    }
    return res;
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int start_,end_,val_;
        scanf("%d %d %d",&start_,&end_,&val_);
        add(start_,end_,val_);
        add(end_,start_,val_);
    }
    int ans=prim();
    if(ans==-1)
        printf("orz\n");
    else printf("%d\n",ans);
    return 0;
}