数据结构精品课件-最小生成树.pptVIP

广度优先生成树森林 a b c h d e k f g 7.5 图的生成树与最小生成树 第 7 章 图 最小生成树(MST)的性质： 求最小生成树的算法较多，主要利用最小生成树性质。 设 N=（V,{E}）是一个连通图，U是V的非空子集，若(u,v)是满足u∈U且v∈V-U的具有最小权值的边, 则必存在一棵包含(u,v)的最小生成树。 可用反证法证明之。 第 7 章 图 7.5 图的生成树与最小生成树 * 设N=(V,{E})是连通网，prim算法步骤为： （1）初始U={u0}(u0∈V),TE=φ； （2）在所有u∈U, v∈V-U的边中选一条代 价最小的边（u0，v0）并入集合TE， 同时将v0并入U； （3）重复（2）,直到U=V,TE含有n-1条边。 此时T=(V,{TE})为N的最小生成树。 第 7 章 图 算法一：普里姆算法 ( Prim ) 步骤: 7.5 图的生成树与最小生成树 * * 第 7 章 图 算法一：普里姆算法 ( Prim ) 实例: a b c d e g f 19 18 27 21 12 7 14 3 16 5 8 a b c d e g f 所得生成树权值 = 14+8+3+5+16+21 = 67 7.5 图的生成树与最小生成树 在生成树的构造过程中,图中 n 个顶点分属两个集合: 已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集 V-U ; 则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。 U V-U 第 7 章 图 算法一：普里姆算法 ( Prim ) 算法思想 7.5 图的生成树与最小生成树 * * 第 7 章 图 算法一：普里姆算法 ( Prim ) 算法思想 连通网用带权的邻接矩阵表示,并设置一个辅助数组closedge[ ], 数组元素下标对应当前V-U集中的顶点序号，元素值则记录该顶点和 U集中相连接的代价最小(最近)边的顶点序号adjvex和权值lowcost. 即对v∈V-U的每个顶点， closedge[v]记录所有与v邻接的、从U到V-U的那组边中的最小边的信息。 7.5 图的生成树与最小生成树 * 第 7 章 图 算法一：普里姆算法 ( Prim ) 算法思想 辅助数组： min{cost(u,v)|u∈U,v∈V-U} closedge[v].lowcost= 0 v∈U closedge[v].adjvex 存放U中与v最近的顶点序号。 struct { vertexData adjvex; int lowcost; } closedge[MAX_VERTEX_NUM]; 7.5 图的生成树与最小生成树 * 7.4 图的应用 第 7 章 图 1.图的连通性问题 ③图的生成树与最小生成树 算法一：普里姆算法 ( Prim ) 算法思想演示 a b c d e g f 19 18 27 21 12 7 14 3 16 5 8 a b c d e g f ∞ 19 ∞ ∞ 14 ∞ 18 19 ∞ 5 7 12 ∞ ∞ ∞ 5 ∞ 3 ∞ ∞ ∞ ∞ 7 3 ∞ 8 21 ∞ 14 12 ∞ 8 ∞ ∞ 16 ∞ ∞ ∞ 21 ∞ ∞ 27 18 ∞ ∞ ∞ 16 27 ∞ lowcost adjvex 7g 6f 5e 4d 3c 2b 1a closedge [v] 0 1a 19 1a 14 1a 18 0 5e 12 5e 8 5e 16 0 4d 7 4d 3 4d 21 0 3c 5 0 0 0 普里姆算法 MiniSpanTree_Prim(AdjMatrix gn, VertexData u) { k=LocateVertex(gn, u); closedge[k].low=0; for (i=0; ign.vnum; i++) if ( i!=k) {closedge[i].vex=u ; closedge[i].low=gn.arcs[k][i].adj;} for (e=1;e=gn.vnum-1