最小生成树课件

最小生成树最小生成树生成树是一个连通图G的一个极小连通子图。包含G的所有n个顶点，但只有n-1条边，并且是连通的。生成树是一个连通图G的一个极小连通子图。包含G的所有n个顶点n当生成树中所包含的边的权值和最小，我们称之为最小生成树。当生成树中所包含的边的权值和最小，我们称之为最小生成树。最小生成树性质最小生成树性质最小生成树的边数必然是顶点数减一，最小生成树的边数必然是顶点数减一，|E|=|V|-1。最小生成树不可以有循环。最小生成树不可以有循环。最小生成树不必是唯一的。最小生成树不必是唯一的。最小生成树性质最小生成树的边数必然是顶点数减一，|E|=n本节所介绍的2种最小生成树算法，都是基于贪心策略。nI.Kruskal算法nII.Prim算法本节所介绍的2种最小生成树算法，都是基于贪心策略。克鲁斯卡尔（Kruskal）算法基本思想：假设 WN=(V,E)是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。应用举例应用举例最小生成树最小生成树克鲁斯卡尔（Kruskal）算法 基本思想：应用举例最小Kruskal 算法过程bchifaedg488414791067211aidcbhgfe12两点属于同一颗树两点属于同一颗树两点属于同一颗树当森林只剩下一棵树时，算法结束Kruskal 算法过程bchifaedg488414791#include#includeusing namespace std;struct Edgeint a,b;/边的两个顶点的编号int d;/边的权值edge11111;int n,m,s;/n为无向图的顶点个数,m为边的条数,s用来存放最小生成树的总权值int root111;/存储父节点bool cmp(Edge a,Edge b)return a.db.d;int find(int a)/寻找父节点if(roota=a)return a;return roota=find(roota);#includebool Union(int a,int b,int d)/合并if(a=b)return 0;/a=b说明边的两个顶点一属于同一颗树，所以不需要合并，直接返回roota=b;/将a的父节点更新为b，从而将树a，b合并成一棵树s+=d;/将边的权值加到s当中return 1;void kruskal()for(int i=0;in;i+)/初始化，将各顶点的父节点标记为本身rooti=i;sort(edge,edge+m,cmp);/将所有边 根据边的权值 从小到大排列 s=0;for(i=0;im;i+)/遍历所有的边if(Union(find(edgei.a),find(edgei.b),edgei.d)n-;/当合并成功，森林的树就少一棵/当遍历完所有的边时,如果n!=1,说明该无向图不是连通图,不存在最小生成树bool Union(int a,int b,int d)/MST性质性质假假设设G=(V,E)是是一一个个无无向向连连通通网网，U是是顶顶点点集集V的的一一个个非非空空子子集集。若若(u,v)是是一一条条具具有有最最小小权权值值的的边边，其其中中uU，vVU，则则必必存存在在一一棵棵包包含含边边(u,v)的的最最小小生成树。生成树。应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树顶点集UuuT1VUvv顶点集T210MST性质假设G=(V,E)是一个无向连通网，U是顶点集VMST性质性质假假设设G=(V,E)是是一一个个无无向向连连通通网网，U是是顶顶点点集集V的的一一个个非非空空子子集集。若若(u,v)是是一一条条具具有有最最小小权权值值的的边边，其其中中uU，vVU，则则必必存存在在一一棵棵包包含含边边(u,v)的的最最小小生成树。生成树。应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树顶点集UuuT1VUvv顶点集T211MST性质假设G=(V,E)是一个无向连通网，U是顶点集V基基本本思思想想：设设G=(V,E)是是具具有有n个个顶顶点点的的连连通通网网，T=(U,TE)是是G的的最最小小生生成成树树，T的的初初始始状状态态为为U=u0（u0V），TE=，重重复复执执行行下下述述操操作作：在在所所有有uU，vV-U的的边边中中找找一一条条代代价价最最小小的的边边(u,v)并并入集合入集合TE，同时，同时v并入并入U，直至，直至U=V。普里姆（普里姆（Prim）算法算法应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树121.初始化：初始化：U=u0（u0V），），TE=;2.循环直到循环直到U=V为止为止2.1在所有在所有uU，vV-U的边中找一条代价最小的边的边中找一条代价最小的边(u,v);2.2TE=TE+(u,v);2.3U=U+v;基本思想：设G=(V,E)是具有n个顶点的连通网，T=(U关键关键:是如何找到连接是如何找到连接U和和V-U的最短边的最短边。普里姆（普里姆（Prim）算法算法应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树利用利用MST性质，可以用下述方法性质，可以用下述方法构造候选最短边集构造候选最短边集：对对V-U中的每个顶点，分别求其到中的每个顶点，分别求其到U的最短边。的最短边。13顶点集UVUuvu顶点集T1T2关键:是如何找到连接U和V-U的最短边。普里姆（Prim）U=AV-U=B,C,D,E,Fcost=(A,B)34,(A,C)46,(A,D),(A,E),(A,F)19251234192646381725应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树ABEDCFPrim算法算法14U=A 251234192646381725应用举例Prim算法算法应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树251234192646381725ABEDCFU=A,FV-U=B,C,D,Ecost=(A,B)34,(F,C)25,(F,D)25,(F,E)2615cost=(A,B)34,(A,C)46,(A,D),(A,E),(A,F)19Prim算法 应用举例最小生成树251234192646Prim算法算法应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树251234192646381725ABEDCFU=A,F,CV-U=B,D,Ecost=(A,B)34,(C,D)17,(F,E)2616cost=(A,B)34,(F,C)25,(F,D)25,(F,E)26Prim算法 应用举例最小生成树251234192646Prim算法算法应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树251234192646381725ABEDCFU=A,F,C,DV-U=B,Ecost=(A,B)34,(F,E)2617cost=(A,B)34,(C,D)17,(F,E)26Prim算法 应用举例最小生成树251234192646Prim算法算法应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树251234192646381725ABEDCFU=A,F,C,D,EV-U=Bcost=(E,B)1218Prim算法 应用举例最小生成树251234192646Prim算法算法应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树251234192646381725ABEDCFU=A,F,C,D,E,BV-U=19Prim算法 应用举例最小生成树251234192646设置一个数组设置一个数组shortEdgen来表示候选最短边集，数来表示候选最短边集，数组元素包括两个域：组元素包括两个域：adjvex和和lowcost。adjvex：表示最短边的邻接点（表示最短边的邻接点（属于集合属于集合U U）下标下标；lowcost：表示最短边的权值，：表示最短边的权值，lowcost=0表示该顶点表示该顶点已加入最小生成树中。已加入最小生成树中。数据结构设计数据结构设计表示表示顶点顶点vi和和vk之间权值为之间权值为w，其中：其中：viV-U 且且vk U shortEdgei.lowcost=wshortEdgei.adjvex=k应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树如何用如何用lowcost和和adjvex表示候选最短边集表示候选最短边集？20设置一个数组shortEdgen来表示候选最短边集，数组i数组数组B(i=1)C(i=2)D(i=3)E(i=4)F(i=5)UV-U输出输出adjvexlowcost03404600019AB,C,D,E,F(AF)19adjvexlowcost034525525526A,FB,C,D,E(FC)25adjvexlowcost034217526A,F,CB,D,E(CD)17adjvexlowcost034526A,F,C,DB,E(FE)26adjvexlowcost412A,F,C,D,EB(EB)12adjvexlowcostA,F,C,D,E,B应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树21 iB(i=1)C(i=2)D(i=3)E(i=1.将顶点将顶点0加入集合加入集合U中；中；2.初始化辅助数组初始化辅助数组shortEdge，分别为，分别为lowcost和和adjvex赋值；赋值；3.重复执行下列操作重复执行下列操作n-1次次3.1在在shortEdge中中选取选取最短边，取其对应的最短边，取其对应的下标下标k；3.2输出边输出边(k,shortEdgek.adjvex)和对应的权值；和对应的权值；3.3将顶点将顶点k加入集合加入集合U中；中；3.4调整调整数组数组shortEdge；应用举例应用举例应用举例应用举例最小生成树最小生成树最小生成树最小生成树Prim算法算法伪代码伪代码221.将顶点0加入集合U中；应用举例最小生成树Prim算Prim算法流程n定义一个点的集合S，集合内的点都是当前所形成的生成树可以到达的。一个点到集合S的距离定义为连结这个点和任意一个集合S内点的边的最小权值。n1.初始化，将任意一点加入集合S。n2.选取含当前未入集合S的点到集合S的最短距离的边，将其加入导出子图，将此点加入集合S，并更新周围点到集合S的距离。n3.重复2过程|V|-1次。n4.所形成的导出子图就是一棵最小生成树Prim算法流程定义一个点的集合S，集合内的点都是当前所形成Prim 算法过程bchifaedg488414791067211aidcbhgfe12全部节点都被覆盖，算法结束Prim 算法过程bchifaedg488414791067 /数组lowcostn：用来保存非生成树中各顶点与生成树中顶点最短边的权值；/数组visn：用来表示顶点v是否已加入最小生成树中。int pos=0;sum=0;/sum用来存放最小生成树的总权值for(i=0;in;i+)/map0i：选取编号为0的顶点加入最小生成树中lowcosti=map0i;/将其余各顶点到编号0顶点的权值存储到lowcost当中visi=0;/起始状态，所有点都未加入到最小生成树中vis0=1;/编号为0的顶点加入最小生成树中 /数组lowcostn：用来for(i=1;in;i+)/n-1次，n为顶点个数Min=999999;for(j=0;jlowcostj&!visj)/寻找满足一个顶点未加入生成树,另一个顶点已加入生成树的最小边Min=lowcostj;pos=j;sum+=Min;vispos=1;/将顶点pos加入生成树for(j=0;jmapposj&!visj)lowcostj=mapposj;for(i=1;in;i+)/n-1次，n为顶点个数