最小生成树算法详解(课堂PPT)

最小生成树算法------prim&Kruskal生成树的概念生成树一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。生成树不唯一V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5生成树最小代价生成树生成树的代价等于其边上的权值之和。V4V1V3V2V6V56512665534V4V1V3V2V6V561654V4V1V3V2V6V512534最小代价生成树两种常用的构造最小生成树的方法：普里姆算法（prim）克鲁斯卡尔算法（Kruskal）普里姆(Prim)算法假设N=(V，E)是连通网，TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V)，TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u，v)中找一条代价最小的边(u0,v0),将其并入集合TE，同时将v0并入U集合。当U=V则结束，此时TE中必有n-1条边，则T=(V，{TE})为N的最小生成树。普里姆算法构造最小生成树的过程是从一个顶点U={u0}作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充到U集合直至U=V为止。V4V1V3V2V6V56512665534V4V1V3V2V6V512534UV-U｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)｛V1,V3,V6｝｛V2,V4,V5｝(2)｛V1,V3,V6,V4｝｛V2,V5｝(3)｛V1,V3,V6,V4,V2｝｛V5｝(4)｛V1,V3,V6,V4,V2,V5｝｛｝(5)最小代价生成树普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止V4V1V3V2V6V5165V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)UV-U普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树V4V1V3V2V6V565V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V6｛V1,V3,V6｝｛V2,V4,V5｝(2)46554UV-U普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树V4V1V3V2V6V565V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V6｛V1,V3,V6｝｛V2,V4,V5｝(2)4655｛V1,V3,V6,V4｝｛V2,V5｝(3)262UV-U普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树V4V1V3V2V6V56V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6｛V1,V3,V6｝｛V2,V4,V5｝(2)465｛V1,V3,V6,V4｝｛V2,V5｝(3)62｛V1,V3,V6,V4,V2｝｛V5｝(4)5UV-U普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树V4V1V3V2V6V5V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5｛V1,V3,V6｝｛V2,V4,V5｝(2)46｛V1,V3,V6,V4｝｛V2,V5｝(3)62｛V1,V3,V6,V4,V2｝｛V5｝(4)5｛V1,V3,V6,V4,V2,V5｝｛｝(5)33UV-U普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止最小代价生成树普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止V4V1V3V2V6V5V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5｛V1,V3,V6｝｛V2,V4,V5｝(2)4｛V1,V3,V6,V4｝｛V2,V5｝(3)2｛V1,V3,V6,V4,V2｝｛V5｝(4)5｛V1,V3,V6,V4,V2,V5｝｛｝(5)3UV-U最小代价生成树普里姆(Prim)算法生成树中只放置一个顶点在关联生成树顶点的边中（即边的一个顶点在生成树中，另一个顶点不在）取权值最小者将选中的边加入生成树，同时将该边的关联顶点加入生成树中生成树中顶点数小于n?是否结束开始从键盘（或数据文件）输入图的信息，用普里姆算法求解给定无向连通图的最小生成树，最后输出最小生成树中的权值和所有的边，图的存储结构自行设定。基本要求例如下图的输出为weight：15(v1,v3)(v3,v6)(v6,v4)(v3,v2)(v2,v5)或者(1,3)(3,6)(6,4)(3,2)(2,5)普里姆算法的实现顶点集合如何表示？最小边如何选择？一个顶点加入U集合（生成树中）如何表示？struct{intadjvex;doublelowcost;}closedge[MAX_VERTEX_NUM];closedge[i].adjvex=kclosedge[i].lowcost顶点i与顶点k邻接顶点k已经在U集合中顶点i加入U集合时=0adjvexlowcostv16v11v15  {v1}{v2,v3,v4,v5,v6}3v2v3v4v5v6UV-Uk顶点iclosedgeclosedge[2].adjvex=1.lowcost=6closedge[3].adjvex=1.lowcost=1closedge[4].adjvex=1.lowcost=5V4V1V3V2V6V5165当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新V4V1V3V2V6V56512665534U集合的成员：V-U集合的成员：closedge[5].adjvex=1.lowcost=∞closedge[6].adjvex=1.lowcost=∞adjvexlowcostv16v11v15  {v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6v2v3v4v5v6UV-Uk顶点iclosedgeV4V1V3V2V6V55564U集合的成员：V-U集合的成员：当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新V4V1V3V2V6V56512665534closedge[2].adjvex=3.lowcost=5closedge[4].adjvex=1.lowcost=5closedge[5].adjvex=3.lowcost=6closedge[6].adjvex=3.lowcost=4adjvexlowcostv16v11v15  {v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4v2v3v4v5v6UV-Uk顶点iclosedgeV4V1V3V2V6V5562V4V1V3V2V6V56512665534当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新U集合的成员：V-U集合的成员：closedge[2].adjvex=3.lowcost=5closedge[4].adjvex=6.lowcost=2closedge[5].adjvex=3.lowcost=6 adjvexlowcostv16v11v15  {v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4adjvexlowcostv3500v360{v1,v3,v6,v4}{v2,v5}v2v3v4v5v6UV-Uk顶点iclosedge2V4V1V3V2V6V556当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新U集合的成员：V-U集合的成员：V4V1V3V2V6V56512665534closedge[2].adjvex=3.lowcost=5closedge[5].adjvex=3.lowcost=6 adjvexlowcostv16v11v15  {v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4adjvexlowcostv3500v360{v1,v3,v6,v4}{v2,v5}2adjvexlowcost000v230{v1,v3,v6,v4,v2}{v5}v2v3v4v5v6UV-Uk顶点iclosedge5V4V1V3V2V6V53当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新V4V1V3V2V6V56512665534U集合的成员：V-U集合的成员： adjvexlowcostv16v11v15  {v1}{v2,v3,v4,v5,v6}3adjvexlowcostv350v15v36v34{v1,v3}{v2,v4,v5,v6}6adjvexlowcostv350v62v360{v1,v3,v6}{v2,v4,v5}4adjvexlowcostv3500v360{v1,v3,v6,v4}{v2,v5}2v2v3v4v5v6UV-Uk顶点iclosedgeV4V1V3V2V6V5adjvexlowcost00000{v1,v3,v6,v4,v2,v5}{} adjvexlowcost000v230{v1,v3,v6,v4,v2}{v5}514253U集合的成员：V-U集合的成员：V4V1V3V2V6V56512665534图采用邻接矩阵表示普里姆算法求最小生成树∞615∞∞6∞5∞3∞15∞5645∞5∞∞2∞36∞∞6∞∞426∞123456123456graph.arac[][]=#include#include#include#defineINIT63355#defineNUM20usingnamespacestd;typedefintElemtype;typedefstructTnode{Elemtypevex[NUM];intarac[NUM][NUM];intv,e;}graph;voidInit_Graph(graph&g){for(inti=1;i<=g.v;i++){for(intj=1;j<=g.v;j++){g.arac[i][j]=INIT;}}}voidCreate_Graph(graph&g){cout<<"输入顶点,边数目:"<>g.v>>g.e;Init_Graph(g);cout<<"输入顶点信息:"<>g.vex[i];}cout<<"输入顶点间下标和权值:"<>k>>t>>w;g.arac[k][t]=w;g.arac[t][k]=g.arac[k][t];}}voidPrim(graph&g){intmin_cost=0;intlowcost[NUM];//当前最短距离intclosest[NUM];//顶点的相邻顶点(closest[i]则为i的邻接点)ints[NUM];//标志访问节点for(inti=1;i<=g.v;i++){closest[i]=1;//初始置各顶点得邻接点为1lowcost[i]=g.arac[1][i];//初始置各顶点的最短距离为1到顶点的距离s[i]=0;}for(inti=1;i"<