图最小生成树2009级.pptxVIP

§7.4 最小的生成树;§7.4 最小的生成树;应用 假设要在 n 个城市之间建立通讯联络网，已知连通 n 个城市各条线路的费用，如何在最节省经费的前提下建立这个通讯网？ 网络中的SpaningTree Protocol 典型算法： 普鲁姆(Prim)算法 克鲁斯卡尔算法;普鲁姆(Prim)算法;普鲁姆(Prim)算法; 普鲁姆算法基本步骤 设U、 MST分别为已在生成树中的顶点集合和边集合。 1）初始时，设U={u0}，MST=?； 2）在所有u?U 、v?V-U的边中选择一条权值最小的边，不妨设为（u,v)； 3）将v加入U；(u,v)加入MST， 4）重复2)、3)，直到U=V为止；;;;3;3;3;3;3;3;3;普鲁姆(Prim)算法;;距离数组Dist[vi]:顶点vi到顶点集U权最小边的 权值(顶点vi到顶点集U的距离);3;3;3;3;3;3;标识数组 Mark[vi]:标识顶点是否已在U中;void MST_Prime(MGraph G,int u0,int Dist[],int MST[],int Mark[]){ //以u0为起点求最小生成树 for (i=0; iG.vexnum; ++i) //初始化 { Mark[i]=0; Dist[i]= G.arcs[u0][i]; if(Dist[i]INFINITY) MST[i]=u0; else MST=-1; }// for Mark[u0]=1; //u0加入U for (i=1; iG.vexnum; ++i) { k=SelectMin(Dist,Mark);//在 Dist中选择最小者 Mark[k]=1; // k加入U for(j=0; jG.vexnum; ++j) //修改V-U中顶点到顶点集U的最短距离 if (!Mark[j]G.arcs[k][j]Dist[j]) { Dist[j]= G.arcs[k][j]; MST[j]=k; } }//for }//MST_Prime ;普里姆算法的性能 设n是图的顶点数,普鲁姆算法的时间复杂度为O(n2)。与边数无关，适用于求边稠密的网的最小生成树。; 克鲁斯卡尔（Kruskual)算法;1) 初始时最小生成树只包含图的n个顶点，每个顶点为一棵子树； 2) 选取权值较小且所关联的两个顶点不在同一子树的边，将此边加入到最小生成树中； 3) 重复2）n-1次，即得到包含n个顶点和n-1条边的最小生成树。 ;;边集ES (((V1,V3),1),( (V4,V6),2),((V2,V5),3),((V3,V6),4), ((V1,V4),5), ((V2,V3),5),((V3,V4),5),(V1,V2),6), ( (V3,V5),6),( (V5,V6),6)));算法描述: ;克鲁斯卡尔的性能 设图的边数是e，克鲁斯卡尔算法的时间复杂度为O(elog e),适用于求边稀疏的网的最小生成树.