算法分析与设计-第06章.pptVIP

南京邮电大学计算机学院*for(i=1;in;i++){for(p=a[k];p;p=p-nextArc){intj=p-adjVex; if((!mark[j])(lowcost[j]p-w)) {lowcost[j]=p-w;nearest[j]=k;}}Tmin=INFTY;for(intj=0;jn;j++)if((!mark[j])(lowcost[j]min)) {min=lowcost[j];k=j;}mark[k]=true;}}南京邮电大学计算机学院*Prim算法时间复杂度分析普里姆算法的时间复杂度是O(n2)。南京邮电大学计算机学院*6.5.4克鲁斯卡尔算法Kruskal在1956年提出的最小代价生成树算法。这种算法对边数较少的带权图有较高效率。南京邮电大学计算机学院*克鲁斯卡尔算法从边的集合E中，按照边的权值从小到大的次序依次选取边加以考察。templateclassTstructeNode{operatorT()const{returnw;} intu,v; Tw;};南京邮电大学计算机学院*克鲁斯卡尔算法描述设G=(V,E)是带权连通图，F=(U,S)是正在构造中的生成树。初始时，U=V,S=?。选边的准则：在E中选择一条最小权值边(u,v),并从E中删除；若在S代表的子图中加入边e=(u,v)后不形成回路，则将其加入S。其含义，u和v不在森林F的同一棵树上，当边(u,v)加入S后,这两棵树合并成一棵树。当S中包含n-1条边时，F=(V,S)就是图G的一棵最小代价生成树。南京邮电大学计算机学院*克鲁斯卡尔算法演示02134512345556660213451234555666南京邮电大学计算机学院*【程序6－9】克鲁斯卡尔算法templateclassTvoidGraphT::Kruskal( PrioQueueeNodeTpq){eNodeTx;UFSets(n);intu,v,k=0;……南京邮电大学计算机学院*while(kn-1!pq.IsEmpty()){pq.Serve(x); u=s.Find(x.u);v=s.Find(x.v); if(u!=v) {s.Union(u,v); k++;cout(x.u,“x.v,x.w);}}coutendl;if(kn-2)throwNonConnected;}南京邮电大学计算机学院*Kruskal算法时间复杂度分析(当图的边数为e，结点数为n时)算法执行前，建立优先权队列的时间为:O(eloge)；Kruskal算法：while循环最多执行e次；循环体中：Serve运算(取最小代价边)的时间为:O(loge)；改进的Find运算(找结点并查集的根)时间为：O(logn)；Union运算(合并两棵并查集树)时间为:O(1)。一般有e≥n，所以所需的计算时间复杂度为：O(eloge)。南京邮电大学计算机学院*6.5.5算法正确性定理6-5设图G=(V,E)是一个带权连通图，U是V的一个真子集。若边(u,v)?E是