最小生成树算法讲解ppt课件.ppt

单元实验五-最小生成树,生成树的概念,生成树一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。生成树不唯一,生成树,最小代价生成树,生成树的代价等于其边上的权值之和。,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,最小代价生成树,两种常用的构造最小生成树的方法：普里姆算法克鲁斯卡尔算法,假设N=(V，E)是连通网，TE是N上最小生成树中边的集合。算法从U=u0(u0V)，TE=开始，重复执行下述操作：在所有uU，vV-U的边(u，v)中找一条代价最小的边(u0,v0),将其并入集合TE，同时将v0并入U集合。当U=V则结束，此时TE中必有n-1条边，则T=(V，TE)为N的最小生成树。普里姆算法构造最小生成树的过程是从一个顶点U=u0作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充到U集合直至U=V为止。,普里姆(Prim)算法,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,V4,V1,V3,V2,V6,V5,1,2,5,3,4,U,V-U,V1,V2,V3,V4,V5,V6,步骤,(0),最小代价生成树,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,V4,V1,V3,V2,V6,V5,1,6,5,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,V4,V1,V3,V2,V6,V5,6,5,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),V6,4,6,5,5,4,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,V4,V1,V3,V2,V6,V5,6,5,V4,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),V6,4,6,5,5,2,6,2,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,V4,V1,V3,V2,V6,V5,6,V4,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),V2,V6,4,6,5,6,2,5,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,V4,V1,V3,V2,V6,V5,V4,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),V2,V6,V5,4,6,6,2,5,3,3,U,V-U,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,最小代价生成树,普里姆算法求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止,V4,V1,V3,V2,V6,V5,V4,V1,V3,1,V1,V2,V3,V4,V5,V6,步骤,(0),V2,V6,V5,4,2,5,3,U,V-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 int adjvex;double lowcost;closedgeMAX_VERTEX_NUM;,closedgei.adjvex=k,closedgei.lowcost,顶点i与顶点k邻接顶点k已经在U集合中,顶点i加入U集合时,普里姆算法的实现,=0,closedge2.adjvex=1.lowcost=6,closedge3.adjvex=1.lowcost=1,closedge4.adjvex=1.lowcost=5,V4,V1,V3,V2,V6,V5,1,6,5,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员：,V-U集合的成员：,closedge5.adjvex=1.lowcost=,closedge6.adjvex=1.lowcost=,V4,V1,V3,V2,V6,V5,5,5,6,4,U集合的成员：,V-U集合的成员：,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,closedge2.adjvex=3.lowcost=5,closedge4.adjvex=1.lowcost=5,closedge5.adjvex=3.lowcost=6,closedge6.adjvex=3.lowcost=4,V4,V1,V3,V2,V6,V5,5,6,2,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员：,V-U集合的成员：,closedge2.adjvex=3.lowcost=5,closedge4.adjvex=6.lowcost=2,closedge5.adjvex=3.lowcost=6,V4,V1,V3,V2,V6,V5,5,6,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员：,V-U集合的成员：,closedge2.adjvex=3.lowcost=5,closedge5.adjvex=3.lowcost=6,V4,V1,V3,V2,V6,V5,3,当U集合中加入一个新顶点时，V-U集合中的顶点到U的最小代价边可能会更新,U集合的成员：,V-U集合的成员：,V4,V1,V3,V2,V6,V5,U集合的成员：,V-U集合的成员：,普里姆算法求最小生成树,6 1 5 6 5 3 1 5 5 6 4 5 5 2 3 6 6 4 2 6,123456,1 2 3 4 5 6,图采用邻接矩阵表示,G.arcs=,#define MaxVnum 50typedef int AdjMatrixMaxVnumMaxVnum;/doubletypedef struct int vexnum,arcnum;/顶点数、边数 AdjMatrix arcs;/邻接矩阵Graph;Graph G;,void MiniSpanTree_PRIM(Graph G,int u)/用普里姆算法从顶点u出发构造G的最小生成树 for(j=0;j G.vexnum;+j)/辅助数组初始化 if(j!=u)closedgej=u,G.arcsuj;,struct int adjvex;double lowcost;closedgeMAX_VERTEX_NUM;,closedgeu.lowcost=0;/初始,U=u for(i=1;i G.vexnum;+i)k=minimum(closedge);/求生成树的下一个顶点k cout closedgek.adjvex G.vexsk;closedgek.lowcost=0;for(j=0;j G.vexnum;+j)if(G.arcskj.adj closedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;/for/MiniSpanTree_PRIM,k=minimum(closedge);/求生成树的下一个顶点k/此时closedgek.lowcost=/MINclosedgevi.lowcost|closedgevi.lowcost0,vi v-u,cout(k,closedgek.adjvex);/输出生成树的边 closedgek.lowcost=0;/顶点k并入U集合,for(j=0;j G.vexnum;+j)if(G.arcskj closedgej.lowcost)closedgej.adjvex=k,closedgej.Lowcost=G.arcskj;,算法的时间复杂度为：O(n2),closedgej.adjvex=u;closedgej.lowcost=G.arcsuj;,选做内容,从键盘输入（或从文件读入）图的信息，用克鲁斯卡尔算法求解给定无向连通图的最小生成树，最后输出最小生成树中的权值和所有的边。,克鲁斯卡尔(Kruskal)算法,假设连通网N=(V，E)，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，)，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。,克鲁斯卡尔算法求最小生成树,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,V4,V1,V3,V2,V6,V5,1,2,3,4,最小代价生成树,克鲁斯卡尔算法求最小生成树,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,V4,V1,V3,V2,V6,V5,1,2,3,4,5,V3、V4依附在同一个连通分量,最小代价生成树,克鲁斯卡尔算法求最小生成树,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,V4,V1,V3,V2,V6,V5,1,2,3,4,V1、V4依附在同一个连通分量,5,最小代价生成树,克鲁斯卡尔算法求最小生成树,V4,V1,V3,V2,V6,V5,6,5,1,2,6,6,5,5,3,4,V4,V1,V3,V2,V6,V5,1,2,5,3,4,最小代价生成树,克鲁斯卡尔(Kruskal)算法,否,将堆顶的边加入生成树后是否形成回路?,在生成树中放置n个孤立顶点,根据边上的权值建小顶堆,是,将该边加入生成树中,去掉堆顶元素，剩余元素重新建堆,生成树中边数小于n-1?,是,否,结束,开始,克鲁斯卡尔(Kruskal)算法,从上述过程可知，实现克鲁斯卡尔(Kruskal)算法时，要解决以下两个问题：如何选择代价最小的边(堆排序，或简单选择排序)；如何判定边所关联的两个顶点是否在同一个连通分量中（集合）,End,