1. 生成树及最小生成树定义
(1)生成树的定义如下：
对于有 n 个顶点的无向连通图 G， 把遍历过程中顺序访问的两个顶点之间的路径记录下
来， 这样 G 中的 n 个顶点以及由出发点一次访问其余 n-1 个顶点所经过的 n-1 条边就构成了
G 的极小连通子图，也就是 G 的一棵生成树，出发顶点是生成树的根。
(2)下面给出最小生成树的概念：
给定一个连通网络， 要求构造具有最小代价的生成树时， 也即使生成树的各边的权值总
和达到最小。 把生成树各边的权值总和定义为生成树的权， 那么具有最小权值的生成树就构
成了连通网络的最小生成树。
 2. 最小生成树的性质
构造最小生成树的算法有很多种，其中大多数的算法都利用了最小生成树的一个性质 ，
简称为 MST 性质：假设 G=（V，E）是一个连通网络，U 是 V 中的一个真子集，若存在顶
点  u ∈U 和顶点v ∈（V-U）的边(u，v)是一条具有最小权值的边，则必存在 G 的一棵最小
生成树包括这条边(u，v)。
 3. 常用算法及思想
利用该性质构造最小生成树的常用算法主要有：Prim(普里姆)算法和 Kruskal(克鲁斯卡
尔)算法。
(1)Prim 算法思想：
设 G=（ V,E ）是一个有 n 个顶点的连通图，用 T=(U，TE)表示要构造的最小生成树， 其
中 U 为顶点集合，TE 为边的集合。则 Prim 算法的具体步骤描述入下：
①初始化：令 U={Ø}，TE={Ø}。从 V 中取出一个顶点u0 放入生成树的顶点集 U 中，作为
第一个顶点，此时T=（{u0}，{ Ø}）；
 ②从  u ∈ U，v ∈（V-U）)  的边(u，v)中找一条代价最小的边（u*，v* ) , 将其放入 TE 中，并
将v *放入 U 中；
 ③重复步骤②，直至 U=V 为止。此时集合 TE 中必有 n-1 条边，T 即为所要构造的最小生
成树。
(2)Kruskal 算法思想：
设 G=（ V,E ）是一个有 n 个顶点的连通图，则令最小生成树的初始状态为只有 n 个顶点
而无任何边的非连通图 T={V,{Ø}},图中每个顶点自成一个连通分量。依次选择 E 中的最小
代价边，若该边依附于 T 中的两个不同的连通分量，则将此边加入到 T 中；否则，舍去此
边而选择下一条代价最小的边。以此类推，直到 T 中所有顶点都在同一连通分量上为止。
这时的 T 就是 G 的一棵最小生成树。
这里就重点讲Kruskal吧。 假设一个邻接矩阵： 0     36    25    16     9    4      1
36   0      28     0      0     0     23
25   28   0        17    0    0      0
16   0     17       0     3     0     0
9     0      0        3      0    15   0
4     0      0        0     15   0     20
1     23    0        0      0     2     0  由于不能截图，所以还是自己动手画一个吧。。。 开始构造时，令T={V，{Ø}}，Cost=0； 2.从图中选择造价最小的边，即为S17，此时 T={{2,3,4,5,6}，{S17 }}，造价 Cost=1 3.接着选择造价第二小的序号 2 的边，即S34，加入 T 中，此时 T={{2,5,6},{S17，S34}}，造价 Cost=1+3=4 4.接着选择造价第三小的序号 3 的边，即S27，加入 T 中，此时 T={{5,6},{S17，S34，S27}}此时 Cost=4+4=8 5.接着选择造价第四小的序号 4 的边， 即S37， 加入 T 中， 此时 T={{5,6},{S17，S34，S27，S37 }} ，Cost=8+9=17 6.选择造价第五小的序号为 5 的边，即S23，由于加入后边S23,S27,S37将构成回路，因此舍弃该边 7.选择造价第六小的序号为 6 的边，即S47，由于加入后边S34，S37，S47将构成回路，因此舍弃该边 8.选择造价第七小的序号为 7 的边，即S45，加入 T 中，此时 T={{6},{S17，S34，S27，S37，S45}}，Cost=17+17=34 9.接着选择造价第八小的序号 8 的边，即S12 ，由于加入后边S12，S27 ，S17 将构成回路，因此舍弃该边 10.选择造价第九小的序号为 9 的边，即S16 ，加入 T 中，此时 T={{Ø},{S17 ，S34，S27，S37，S45，S16}}，Cost=34+23=57 11.算法结束
此时，所有顶点已包含在树中，整棵最小生成树已经构造完成。包括点{（1,7） ，（2,7） ， （3,7） ， （3,4） ， （4,5） ， （1,6）}，此时最小生成树的权值和为57
呼呼，终于打完了。虽然这个例子是直接借用的，但是也是比较费事滴。。。 附上自己的代码，注意，我用的是并查集来判断是否成为一个环。 #include
#include
#include
#include
#include
#include
using namespace std;
int Cnt,Ans,n,top,m,x,y,z;
int f[100000];
struct edge
{
int u,v,w;
}E[100000];
bool cmp(edge e1,edge e2)
{
return e1.w }
int  find(int x)
{
if(f[x]==x) return f[x];
f[x]=find(f[x]);
return f[x];
}
void UN(int x,int y)
{
f[x]=y;
/*
int q=find(x);
int p=find(y);
f[p]=q;
*/
}
void Kruskal()
{
sort(E+1,E+top+1,cmp);
for (int i=1;i<=n;i++)
f[i]=i;
Ans=0;Cnt=0;int fx,fy;
for (int i=1;i<=top;i++)
{
fx=find(E[i].u);fy=find(E[i].v);
if(fx==fy) continue;
Ans+=E[i].w;
Cnt++;
UN(fx,fy);
if(Cnt==n-1) break;
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
top++;
E[i].u=x;
E[i].v=y;
E[i].w=z;
}
Kruskal();
printf("%d ",Ans);
return 0;
}