最小生成树

最小生成树生成树是一个连通图G的一个极小连通子图。包含G的所有n个顶点，但只有n-1条边，并且是连通的。当生成树中所包含的边的权值和最小，我们称之为最小生成树。最小生成树性质最小生成树的边数必然是顶点数减一，|E|=|V|-1。最小生成树不可以有循环。最小生成树不必是唯一的。本节所介绍的2种最小生成树算法，都是基于贪心策略。I.Kruskal算法II.Prim算法克鲁斯卡尔（Kruskal）算法基本思想：假设WN=(V,{E})是一个含有n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。应用举例——最小生成树Kruskal算法过程bchifaedg488414791067211aidcbhgfe12两点属于同一颗树两点属于同一颗树两点属于同一颗树当森林只剩下一棵树时，算法结束#includeiostream#includealgorithmusingnamespacestd;structEdge{inta,b;//边的两个顶点的编号intd;//边的权值}edge[11111];intn,m,s;//n为无向图的顶点个数,m为边的条数,s用来存放最小生成树的总权值introot[111];//存储父节点boolcmp(Edgea,Edgeb){returna.db.d;}intfind(inta)//寻找父节点{if(root[a]==a)returna;returnroot[a]=find(root[a]);}boolUnion(inta,intb,intd)//合并{if(a==b)return0;//a==b说明边的两个顶点一属于同一颗树，所以不需要合并，直接返回root[a]=b;//将a的父节点更新为b，从而将树a，b合并成一棵树s+=d;//将边的权值加到s当中return1;}voidkruskal(){for(inti=0;in;i++)//初始化，将各顶点的父节点标记为本身root[i]=i;sort(edge,edge+m,cmp);//将所有边根据边的权值从小到大排列s=0;for(i=0;im;i++)//遍历所有的边{if(Union(find(edge[i].a),find(edge[i].b),edge[i].d))n--;//当合并成功，森林的树就少一棵}//当遍历完所有的边时,如果n!=1,说明该无向图不是连通图,不存在最小生成树}MST性质假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。应用举例——最小生成树顶点集Uu'uT1V－Uvv'顶点集T210MST性质假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。应用举例——最小生成树顶点集Uu'uT1V－Uvv'顶点集T211基本思想：设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树，T的初始状态为U={u0}（u0∈V），TE={}，重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u,v)并入集合TE，同时v并入U，直至U=V。普里姆（Prim）算法应用举例——最小生成树121.初始化：U={u0}（u0∈V），TE={};2.循环直到U=V为止2.1在所有u∈U，v∈V-U的边中找一条代价最小的边(u,v);2.2TE=TE+{(u,v)};2.3U=U+{v};关键:是如何找到连接U和V-U的最短边。普里姆（Prim）算法应用举例——最小生成树利用MST性质，可以用下述方法构造候选最短边集：对V-U中的每个顶点，分别求其到U的最短边。13顶点集UV－Uu'vu顶点集T1T2U={A}V-U={B,C,D,E,F}cost={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}251234192646381725应用举例——最小生成树ABEDCFPrim算法14Prim算法应用举例——最小生成树251234192646381725ABEDCFU={A,F}V-U={B,C,D,E}cost={(A,B)34,(F,C)25,(F,D)25,(F,E)26}15cost'={(A,B)34,(A,C)46,(A,D)∞,(A,E)∞,(A,F)19}Prim算法应用举例——最小生成树251234192646381725ABEDCFU={A,F,C}V-U={B,D,E}cost={(A,B)34,(C,D)17,(F,E)26}16cost'={(A,B)34,(F,C)25,(F,D)25,(F,E)26}Prim算法应用举例——最小生成树251234192646381725ABEDCFU={A,F,C,D}V-U={B,E}cost={(A,B)34,(F,E)26}17cost'={(A,B)34,(C,D)17,(F,E)26}Prim算法应用举例——最小生成树251234192646381725ABEDCFU={A,F,C,D,E}V-U={B}cost={(E,B)12}18Prim算法应用举例——最小生成树251234192646381725ABEDCFU={A,F,C,D,E,B}V-U={}19设置一个数组shortEdge[n]来表示候选最短边集，数组元素包括两个域：adjvex和lowcost。adjvex：表示最短边的邻接点（属于集合U）下标；lowcost：表示最短边的权值，lowcost=0表示该顶点已加入最小生成树中。数据结构设计表示顶点vi和vk之间权值为w，其中：vi∈V-U且vk∈UshortEdge[i].lowcost=wshortEdge[i].adjvex=k应用举例——最小生成树如何用lowcost和adjvex表示候选最短边集？20i数组B(i=1)C(i=2)D(i=3)E(i=4)F(i=5)UV-U输出adjvexlowcost0340460∞0∞019{A}{B,C,D,E,F}(AF)19adjvexlowcost034525525526{A,F}{B,C,D,E}(FC)25adjvexlowcost034217526{A,F,C}{B,D,E}(CD)17adjvexlowcost034526{A,F,C,D}{B,E}(FE)26adjvexlowcost412{A,F,C,D,E}{B}(EB)12adjvexlowcost{A,F,C,D,E,B}{}应用举例——最小生成树211.将顶点0加入集合U中；2.初始化辅助数组shortEdge，分别为lowcost和adjvex赋值；3.重复执行下列操作n-1次3.1在shortEdge中选取最短边，取其对应的下标k；3.2输出边(k,shortEdge[k].adjvex)和对应的权值；3.3将顶点k加入集合U中；3.4调整数组shortEdge；应用举例——最小生成树Prim算法——伪代码22Prim算法流程定义一个点的集合S，集合内的点都是当前所形成的生成树可以到达的。一个点到集合S的距离定义为连结这个点和任意一个集合S内点的边的最小权值。1.初始化，将任意一点加入集合S。2.选取含当前未入集合S的点到集合S的最短距离的边，将其加入导出子图，将此点加入集合S，并更新周围点到集合S的距离。3.重复2过程|V|-1次。4.所形成的导出子图就是一棵最小生成树Prim算法过程bchifaedg488414791067211aidcbhgfe12全部节点都被覆盖，算法结束//数组lowcost[n]：用来保存非生成树中各顶点与生成树中顶点最短边的权值；//数组vis[n]：用来表示顶点v是否已加入最小生成树中。intpos=0;sum=0;//sum用来存放最小生成树的总权值for(i=0;in;i++)//{//map[0][i]：选取编号为0的顶点加入最小生成树中lowcost[i]=map[0][i];//将其余各顶点到编号0顶点的权值存储到lowcost当中vis[i]=0;//起始状态，所有点都未加入到最小生成树中}vis[0]=1;//编号为0的顶点加入最小生成树中for(i=1;in;i++)//n-1次，n为顶点个数{Min=999999;for(j=0;jn;j++){if(Minlowcost[j]&&!vis[j])//寻找满足一个顶点未加入生成树,另一个顶点已加入生成树的最小边{Min=lowcost[j];pos=j;}}sum+=Min;vis[pos]=1;//将顶点pos加入生成树for(j=0;jn;j++)//更新由顶点pos到其他未加入生成树的顶点边的权值{if(lowcost[j]map[pos][j]&&!vis[j])lowcost[j]=map[pos][j];}}