最小生成树 首先，生成树是建立在无向图中的，对于有向图，则没有生成树的概念，所以接下来讨论的图均默认为无向图。对于一个有n个点的图，最少需要n-1条边使得这n个点联通，由这n-1条边组成的子图则称为原图的生成树。一般来说，一个图的生成树并不是唯一的（除非原图本身就是一棵树）。 现在考虑带权图G，即图的边带权，则最小生成树就是在G中权值和最小的一颗生成树，显然最小生成树也不是唯一的，但是其权值唯一。有很多应用需要用到最小生成树的概念，比较直观的一个应用就是：有n个村庄，现在要在这些村庄之间修一些路，其中村庄i和村庄j之间的距离是Dij，现在要修最短的路使得所有村庄连接起来。 显然，这个问题可以直接套用最小生成树模型，找出最小生成树即找到了一个方案。
对于如何寻找一个带权图的最小生成树，已经有了专门的求解方法，在具体讲解这些算法之前，我们这里先来挖掘一下最小生成树的一些特性，即一颗生成树要成为最小生成树，需要满足什么条件。
MST性质： 设一个带权无向图G（V,E,W） （V代表点集，E代表边集，W代表权值集），且T为Ｇ的一颗生成树，对于Ｅ中任意一条不属于Ｔ的边ｅ，将其加入Ｔ中，会产生一条环（否则T不连通），如果e始终是环中权值最大的一条边，那么说明T满足MST性质。
以上是MST性质的定义，其中MST就是最小生成树的意思，但是现在并没有证明这个性质和最小生成树有什么关系，接下来将要证明，一颗生成树是最小生成树，当且仅当它满足MST性质。
引理1：对于图Ｇ（V,E,W）的两颗生成树T1和T2，若它们都满足MST性质，则它们的权值和相同。
证明：运用数学归纳法证明当有k条边在T1中而不在T2中时（0<=k<=n-1，同样的，这是也有k条边在T2中而不在T1中），T1的权值和等于T2的权值和。
1：首先，当k=0时，说明T1和T2的所有边都一样，则T1和T2是同一颗生成树，显然它们的权值和相等。 2：现在设当k
//Prim struct edge{ int to,len,next; }e[maxm]; int box[maxn],cnt,used[maxn]; void init(int n){ for(int i=0;i<=n;i++)box[i]=-1; cnt=0; } void add(int from,int to,int len){ e[cnt].to=to; e[cnt].len=len; e[cnt].next=box[from]; box[from]=cnt++; } struct node{ int v,len; node(){} node(int x,int y):v(x),len(y){} bool operator<(const node &x)const{ return len>x.len; } }; priority_queue<node> pq; int Prim(int n,int m){ memset(used,0,sizeof(used));//初始化所有点，设状态为unseen int num=0,sum=0,now=1; do{ used[now]=1; for(int t=box[now];t+1;t=e[t].next){ int v=e[t].to,len=e[t].len; if(!used[v])pq.push(node(v,len)); } while(!pq.empty()){ node tmp=pq.top();pq.pop(); int v=tmp.v,len=tmp.len; if(used[v])continue; now=v; sum+=len; break; } num++; }while(num<n); return sum; }现在来看看为什么Prim算法是正确的。 首先，如果一个图存在最小生成树，那么由上面的算法得到的一定是一颗生成树。因为当算法结束时，所有的点均为tree点，说明所有点都连通。并且得到的子图不会存在环，因为我们增加一条边时，这条边连接的一定是一个tree点和一个finge点，只有连接两个tree点时才会产生环。 前面的定理1告诉我们，一颗生成树是最小生成树，那么当且仅当它满足MST性质，那么我们只要证明Prim算法得到的生成树满足MST性质即可。
定理2：设带全图G(V,E,W)存在最小生成树，那么Prim算法得到的生成树就是G的最小生成树。
证明：我们只要证明，Prim算法得到的生成树满足MST性质即可，这可由归纳法证明。下面证明，当加入第k个点时（1<=k<=n），Prim算法得到生成树满足MST性质：
1：当k=1时，只有一个点，显然满足MST性质。 2：当k>1时，我们假设当1k
#define maxn 110 #define maxm 10010 using namespace std; int uf[maxn]; struct edge{ int u,v,len; }e[maxm]; bool cmp(const edge &x,const edge &y){ return x.len<y.len; } void init(int n){//初始化并查集 for(int i=0;i<=n;i++)uf[i]=i; } int find(int x){ if(x==uf[x])return x; return uf[x]=find(uf[x]); } int Union(int x,int y){//合并两个集合（如果x,y在同一集合，返回0，否则返回1） x=find(x),y=find(y); if(x!=y){ uf[x]=y; return 1; } return 0; } int Kruskal(int n,int m){//n个点，m条边 sort(e,e+m,cmp);//排序 int sum=0;//最小生成树的权值和 for(int i=0;i<m;i++){//从小到大枚举边 int u=e[i].u,v=e[i].v,len=e[i].len; sum+=len*Union(u,v); } return sum;//返回权值和 }Kruskal算法的正确性
同Prim算法正确性证明一样，我们只要证明Kruskal算法得到的生成树满足MST性质即可。首先，如果G存在最小生成树，那么Kruskal算法得到肯定是一颗生成树。这点就不证明了，用反证法可以很容易证明。
定理3：设带全图G(V,E,W)存在最小生成树，那么Kruskal算法得到的生成树就是G的最小生成树。
证明：设Kruskal算法结束时得到的生成树为T，假设T不满足MST性质，那么存在一条边e（u，v），它不属于T，将e加入T中后，得到一个环。设环中存在一条（可能是多条）边e’，其权值大于e。那么由Kruskal算法的步骤，可知，e在e’之前枚举。当枚举e’之前，可知u,v一定不在同一个集合中，否则e’就不会在T中了。那么既然在e’加入之前，u，v不在同一个集合中，那么枚举e时(e在e’加入前被枚举),根据Kruskal算法的步骤3，可知e一定在T中，但是e并不在T中，矛盾，所以加入e后，所得到的环中e的权值最大。这就表示T满足MST性质。从而由定理1，可知T是Ｇ的一颗最小生成树。证毕。
总结：到此为止，最小生成树的总结就写完了，介绍的两个算法都是基于贪心思想的应用。个人觉得学习算法一定不能仅仅记住算法的代码实现，一定还要理解其中的思想和正确性。只有这样才能真正了解一个算法的精髓。就算是忘了代码的实现，理解了思想也能自己推出来。这应该才是学习的不二法门吧。
