最小生成树 首先,生成树是建立在无向图中的,对于有向图,则没有生成树的概念,所以接下来讨论的图均默认为无向图。对于一个有n个点的图,最少需要n-1条边使得这n个点联通,由这n-1条边组成的子图则称为原图的生成树。一般来说,一个图的生成树并不是唯一的(除非原图本身就是一棵树)。 现在考虑带权图G,即图的边带权,则最小生成树就是在G中权值和最小的一颗生成树,显然最小生成树也不是唯一的,但是其权值唯一。有很多应用需要用到最小生成树的概念,比较直观的一个应用就是:有n个村庄,现在要在这些村庄之间修一些路,其中村庄i和村庄j之间的距离是Dij,现在要修最短的路使得所有村庄连接起来。 显然,这个问题可以直接套用最小生成树模型,找出最小生成树即找到了一个方案。
对于如何寻找一个带权图的最小生成树,已经有了专门的求解方法,在具体讲解这些算法之前,我们这里先来挖掘一下最小生成树的一些特性,即一颗生成树要成为最小生成树,需要满足什么条件。
MST性质: 设一个带权无向图G(V,E,W) (V代表点集,E代表边集,W代表权值集),且T为G的一颗生成树,对于E中任意一条不属于T的边e,将其加入T中,会产生一条环(否则T不连通),如果e始终是环中权值最大的一条边,那么说明T满足MST性质。
以上是MST性质的定义,其中MST就是最小生成树的意思,但是现在并没有证明这个性质和最小生成树有什么关系,接下来将要证明,一颗生成树是最小生成树,当且仅当它满足MST性质。
引理1:对于图G(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是G的一颗最小生成树。证毕。
总结:到此为止,最小生成树的总结就写完了,介绍的两个算法都是基于贪心思想的应用。个人觉得学习算法一定不能仅仅记住算法的代码实现,一定还要理解其中的思想和正确性。只有这样才能真正了解一个算法的精髓。就算是忘了代码的实现,理解了思想也能自己推出来。这应该才是学习的不二法门吧。