最小生成树算法

北京大学暑期课《ACM/ICPC竞赛训练》北京大学信息学院郭炜[e-mail]课程网页：最小生成树(MST)问题本文大量内容引自北京大学信息学院程序设计实习（实验班）郑聃崴、陈国鹏等同学的讲义，在此致谢图的生成树在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，即：V(G’)=V(G);E(G’)∈E(G)若边集E(G’)中的边既将图中的所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。一棵含有n个点的生成树，必含有n-1条边。最小生成树对于一个连通网（连通带权图，假定每条边上的权均为大于零的实数）来说，每棵树的权（即树中所有边的权值总和）也可能不同具有权最小的生成树称为最小生成树。最小生成树生成树无向连通图的边的集合无回路连接所有的点最小所有边的权值之和最小Prim算法假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U,TE初值均为空集。首先从V中任取一个顶点（假定取v1），将它并入U中，此时U={v1}，然后只要U是V的真子集(U∈V)，就从那些一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短边，设为(vi,vj),其中vi∈U,vj∈V-U，并把该边(vi,vj)和顶点vj分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后得到最小生成树。图例关键问题每次如何从连接T中和T外顶点的所有边中，找到一条最短的1)如果用邻接矩阵存放图，而且选取最短边的时候遍历所有点进行选取，则总时间复杂度为O(V2),V为顶点个数2)用邻接表存放图,并使用堆来选取最短边，则总时间复杂度为O(ElogV)不加堆的Prim算法适用于密集图，加堆的适用于稀疏图POJ1258最小生成树模版题输入图的邻接矩阵，求最小生成树的总权值(多组数据）输入样例：40492140817980162117160输出样例：28prioirty_queue实现Prim+堆完成POJ1258//byGuoWei#includeiostream#includevector#includealgorithm#includequeueusingnamespacestd;constintINFINITE=130;structEdge{intv;//边端点，另一端点已知intw;//边权值，也用来表示v到在建最小生成树的距离Edge(intv_=0,intw_=INFINITE):v(v_),w(w_){}booloperator(constEdge&e)const{returnwe.w;//在队列里，边权值越小越优先}};vectorvectorEdgeG(110);//图的邻接表intHeapPrim(constvectorvectorEdge&G,intn)//G是邻接表,n是顶点数目，返回值是最小生成树权值和{inti,j,k;EdgexDist(0,0);priority_queueEdgepq;//存放顶点及其到在建生成树的距离vectorintvDist(n);//各顶点到已经建好的那部分树的距离vectorintvUsed(n);//标记顶点是否已经被加入最小生成树intnDoneNum=0;//已经被加入最小生成树的顶点数目for(i=0;in;i++){vUsed[i]=0;vDist[i]=INFINITE;}nDoneNum=0;intnTotalW=0;//最小生成树总权值pq.push(Edge(0,0));//开始只有顶点0，它到最小生成树距离0while(nDoneNumn&&!pq.empty()){do{//每次从队列里面拿离在建生成树最近的点xDist=pq.top();pq.pop();}while(vUsed[xDist.v]==1&&!pq.empty());if(vUsed[xDist.v]==0){nTotalW+=xDist.w;vUsed[xDist.v]=1;nDoneNum++;for(i=0;iG[xDist.v].size();i++){//更新新加入点的邻点intk=G[xDist.v][i].v;if(vUsed[k]==0){intw=G[xDist.v][i].w;if(vDist[k]w){vDist[k]=w;pq.push(Edge(k,w));}}}}}if(nDoneNumn)return-1;//图不连通returnnTotalW;}intmain(){intN;while(cinN){for(inti=0;iN;++i)G[i].clear();for(inti=0;iN;++i)for(intj=0;jN;++j){intw;cinw;G[i].push_back(Edge(j,w));}coutHeapPrim(G,N)endl;}}Kruskal算法假设G=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，U=V,TE初值为空。将图G中的边按权值从小到大依次选取，若选取的边使生成树不形成回路，则把它并入TE中，若形成回路则将其舍弃，直到TE中包含N-1条边为止，此时T为最小生成树。关键问题如何判断欲加入的一条边是否与生成树中边构成回路。将各顶点划分为所属集合的方法来解决，每个集合的表示一个无回路的子集。开始时边集为空，N个顶点分属N个集合，每个集合只有一个顶点，表示顶点之间互不连通。当从边集中按顺序选取一条边时，若它的两个端点分属于不同的集合，则表明此边连通了两个不同的部分，因每个部分连通无回路，故连通后仍不会产生回路，此边保留，同时把相应两个集合合并Kruskal算法完成POJ1258//byGuoWei#includeiostream#includevector#includealgorithmusingnamespacestd;structEdge{ints,e,w;//起点，终点，权值Edge(intss,intee,intww):s(ss),e(ee),w(ww){}Edge(){}booloperator(constEdge&e1)const{returnwe1.w;}};vectorEdgeedges;vectorintparent;intGetRoot(inta){if(parent[a]==a)returna;parent[a]=GetRoot(parent[a]);returnparent[a];}voidMerge(inta,intb){intp1=GetRoot(a);intp2=GetRoot(b);if(p1==p2)return;parent[p2]=p1;}intmain(){intN;while(cinN){parent.clear();edges.clear();for(inti=0;iN;++i)parent.push_back(i);for(inti=0;iN;++i)for(intj=0;jN;++j){intw;cinw;edges.push_back(Edge(i,j,w));}sort(edges.begin(),edges.end());intdone=0;inttotalLen=0;for(inti=0;iedges.size();++i){if(GetRoot(edges[i].s)!=GetRoot(edges[i].e)){Merge(edges[i].s,edges[i].e);++done;totalLen+=edges[i].w;}if(done==N–1)break;}couttotalLenendl;}}算法：Kruskal和Prim•Kruskal:将所有边从小到大加入，在此过程中判断是否构成回路–使用数据结构：并查集–时间复杂度：O(ElogE)–适用于稀疏图•Prim:从任一节点出发，不断扩展–使用数据结构：堆–时间复杂度：O(ElogV)或O(VlogV+E)(斐波那契堆）–适用于密集图–若不用堆则时间复杂度为O(V2)例题：POJ2349ArcticNetwork•某地区共有n座村庄，每座村庄的坐标用一对整数(x,y)表示，现在要在村庄之间建立通讯网络。•通讯工具有两种，分别是需要铺设的普通线路和无线通讯的卫星设备。•只能给k个村庄配备卫星设备，拥有卫星设备的村庄互相间直接通讯。•铺设了线路的村庄之间也可以通讯。但是由于技术原因，两个村庄之间线路长度最多不能超过d,否则就会由于信号衰减导致通讯不可靠。要想增大d值，则会导致要投入更多的设备（成本）例题：POJ2349ArcticNetwork已知所有村庄的坐标(x,y)，卫星设备的数量k。问：如何分配卫星设备，才能使各个村庄之间能直接或间接的通讯，并且d的值最小？求出d的最小值。数据规模：0=k=n=500(FromWaterlooUniversity2002)思路假设d已知，把所有铺设线路的村庄连接起来，构成一个图。需要卫星设备的台数就是图的连通支的个数。d越小，连通支就可能越多。那么，只需找到一个最小的d，使得连通支的个数小于等于卫星设备的数目。答案把整个问题看做一个完全图，村庄就是点，图上两点之间的边的权值，就是两个村庄的直线距离。只需在该图上求最小生成树，d的最小值即为第K长边！因为：最小生成树中的最长k-1条长边都去掉后，正好将原树分成了k个连通分支，在每个连通分支上摆一个卫星设备即可为什么d不可能比第k长边更小？假设最小生成树T上，第k长边连接的点是a,b，那么将边a,b去掉后，树就分成了两个部分T1和T2要使T1和T2能够通讯，必须在T1中找一点p和T2中的点q相连，若边p,q的长度小于a,b，则在T上用p,q替换a,b就能得到更小的生成树，矛盾。因此找不到长度小于a,b的p,q。对任何比第k长边短的边e，同理也不可能找到替代e的边。因此d不可能更小了最小生成树可能不止一棵，为什么第k长边长度一定相同？因为有以下结论：一个图的两棵最小生成树，边的权值序列排序后结果相同证明：假设某个最小生成树T1的边权从小到大排序后的序列为:a1,a2….an某个最小生成树T2的边权从小到大排序后的序列为:b1,b2…bn两者若不同，则必然存在一个最小的i,使得aibi假设T2中有m条边的权为bi，那么，T1中最多只有m-1条边的权和bi相同。但是对于T2中任何一条不在T1中的权为bi的边，如果将其从T2去掉，则T2被分成A,B两个部分。那么在T1中连接A,B这两个部分的边，必然权值是等于bi的，否则经过替换，要么T1的权值可以变得更小，要么T2的权值可以变得更小，这和T1,T2是最小生成树矛盾。对T2中每个权值为bi的边，都可以在T1中找到一个权值相同且不在T2的边与其对应，而这些边由于是连接不同部分的，所以不可能相同，因此，在T1中也应该有m条权值为bi的边，这和T1中最多m-1条权值为bi的边矛盾。因此，不存在i,使得的aibi，即两个边权序列应该相同。次小生成树例题4：POJ1679TheUniqueMST题目：要求判断给定图的最小生成树是否唯一解：显然，这是一个求次小生成树的问题，如果求出来的次小生成树权值和与最小生成树相同，则不唯一次小生成树的定义设G=(V,E,ω)是连通的无向图，T是图G的一个最小生成树。如果有另一棵树T1，满足不存在树T’,T’≠T,ω（T’）ω（T1），则称T1是图G的次小生成树。次小生成树有可能也是最小生成树定理1最小生成树的邻集里包含次小生成树。即可以通过由最小生成树换一条边来得到