74最小生成树 、最小生成树概念 1.设无向连通图G(V,{E}), 其子图G=(V,{})满足: ①V(G)=V(G)n个顶点 ②G是连通的 ③G中无回路 则G是G的生成树
7.4 最小生成树 一、最小生成树概念 1. 设无向连通图G=（V，{E}）， 其子图G’=（V，{T}）满足： ① V(G’)=V(G) n个顶点 ② G’是连通的 ③ G’中无回路 则G’是G的生成树
74最小生成树 具有n个顶点的无向连通图G 其任一生成G恰好含n-1条边 生成树不一定唯一,如 4个顶点选择3条边有 如下5种形状(5×4=20种) 其中16种为生成树,(保证了连通)
7.4 最小生成树 具有n个顶点的无向连通图G • 其任一生成G’恰好含n-1条边 • 生成树不一定唯一，如 4个顶点选择3条边有 如下5种形状(5×4= 20种): 其中16种为生成树,（保证了连通）
7.4最小生成树 生成树代价 对图中每条边赋于一个权值(代价),则构成一个网, 网的生成树G=N,{}的代价是T中各边的权值之和, 最小生成树就是网上所有可能的生成树中,代价最小 的一类生成树 最小生成树也不一定唯一
生成树代价 对图中每条边赋于一个权值（代价），则构成一个网， 网的生成树G’=(V，{T})的代价是T中各边的权值之和， 最小生成树就是网上所有可能的生成树中，代价最小 的一类生成树。 最小生成树也不一定唯一。 7.4 最小生成树
7.4最小生成树 最小生成树的实用例子很多 顶点表示 computer 例1:N台计算机之间建立通讯网边表示通讯线 权值表示通讯线的代价(通讯 线长度, computer间距离等) 要求: ①n台计算机中的任何两台能通过网进行通讯; ②使总的代价最小。 求最小生成树[们
最小生成树的实用例子很多 例1： N台计算机之间建立通讯网 顶点表示computer 边表示通讯线 权值表示通讯线的代价（通讯 线长度，computer间距离等） 要求： ① n台计算机中的任何两台能通过网进行通讯； ② 使总的代价最小。-------求最小生成树[T] 7.4 最小生成树
7.4最小生成树 最小生成树的实用例子 顶点表示投递点 例2:邮递员送信线路]边表示街道 权值表示街道的长度 要求: ①完成n个投递点的投递; ②使总路径长度最短,即求最小生成树[们
最小生成树的实用例子 例2：邮递员送信线路[T] 顶点表示投递点 边表示街道 权值表示街道的长度 要求： ① 完成n个投递点的投递； ② 使总路径长度最短, 即求最小生成树[T] 7.4 最小生成树
、最小生成树性质MST 设N=(V,{E})是一个连通网, U是顶点集V的一个非空子集。 若(u,v)是一条具有最小权值的边,其中u∈U,v∈V-U, 即(u,v)=Min{cost(x,y)|x∈U,y∈V-U} 则必存在一棵包含边(u,v)的最小生成树。 含义:将顶点分为两个不相交的集合U和VU, 若边(u,v)是连接这两个顶点集的最小权值 边,则边(u,v)必然是某最小生成树的边
二、最小生成树性质MST 设N=（V，{E}）是一个连通网， U是顶点集V的一个非空子集。 若（u，v）是一条具有最小权值的边，其中u∈U,v∈V-U, 即（u，v）=Min{cost(x,y)|x∈U,y∈V-U} 则必存在一棵包含边（u，v）的最小生成树。 u v-u u v u’ v’ 含义：将顶点分为两个不相交的集合U和V-U， 若边（u，v）是连接这两个顶点集的最小权值 边，则边（u，v）必然是某最小生成树的边
三、普里姆(Pim)最小生成树算法 设N=(V,{E})是一个连通网, V=[1,2,…,m}是N的顶点集合, 辅助集合U,初值为{Uo}, 用来存放当前所得到的最小生成树的顶点; 辅助集合TE,初值为旮}, 用来存放当前所得到的最小生成树的边
三、普里姆（Prim）最小生成树算法 设 N=（V，{E}）是一个连通网， V=[1，2，…，n}是N的顶点集合， 辅助集合U，初值为{Uo}， 用来存放当前所得到的最小生成树的顶点； 辅助集合TE，初值为{}， 用来存放当前所得到的最小生成树的边
Prim算法步骤 1.TE=Φ,U={u 2.当U≠V,重复下列步骤 (1)选取(u2V)=min{cost(u,v)u∈U,v∈V-U},保证不 形成回路 (2)TE=TE+(u,Vo),边(lmv)并入E (3)U=U+{V},顶点并入U 第3步 初始化:① ③ 第1步:1 第4步:②5④ 第5步 ① 特点:以连通为主第2步 选代价最小的邻接边 4
Prim算法步骤 1. TE=Ф,U={u0} 2. 当U≠V，重复下列步骤： (1)选取（u0,v0)=min{cost(u,v)|u∈U,v∈V-U}，保证不 形成回路 (2)TE=TE+（u0,v0), 边（u0,v0)并入TE (3)U=U+{V0}，顶点V0 并入U 初始化： ① ② ① ④ ⑤ 5 2 1 ③ 3 4 6 6 5 5 6 ⑥ ① 1 ③ 第1步： 6 ① 1 ③ 4 第2步： ④ 6 ① 1 ③ 4 2 第3步： ② 5 ④ 6 ① 1 ③ 4 2 第4步： 2 3 ⑤ ② 5 ④ 6 ① 1 ③ 4 特点: 以连通为主 第5步： 选代价最小的邻接边
Prim算法实现:见书P175 算法 minispantree PRIM的几点说明: 1.G为网的邻接矩阵 即 G arcs,J=w或为无穷大 2.辅助数组 closedgel1m有两个分量: closedgelk]. adjvex存放边(k,j)依附的另一顶点j(j∈U closedge klowcost存放边(k,j)的权值,当值为0时,表示顶 点k已加入到集合U中。 ·区别顶点∈U或∈VU,是根据,, lowcost=0∈U . lowcost〉0∈VU closedgek-adjvex∈U而k∈U
算法minispantree_PRIM的几点说明: 1. G为 网的邻接矩阵 即 G.arcs[i, j]=wij 或 为无穷大 2. 辅助数组closedge[1..n] 有两个分量: closedge[k].adjvex存放边(k, j)依附的另一顶点j( j∈U) closedge[k].lowcost存放边(k, j)的权值，当值为0时，表示顶 点k已加入到集合U中。 • 区别顶点∈U或∈V-U，是根据，.lowcost=0 ∈U .lowcost 〉0 ∈V-U • closedge[k].adjvex ∈U 而 k ∈V-U Prim算法实现:见书P175
算法 minispantree PRIM的几点说明: 3. int minimum(closedge) i min=oo; h=1; for(k1; k<= vtxnum k++) if ((closedgek.lowcost!=0)&&(closedge( k] .lowcost<min)) f min:=closedge[ k -lowcost; h: =k;) return h: }∥ minimun
算法minispantree_PRIM的几点说明: 3. int minimum(closedge) { min=∞; h=1; for ( k=1;k<= vtxnum ;k++) if ((closedge[k].lowcost!=0)&&(closedge[k].lowcost<min)) { min:=closedge[k].lowcost; h:=k;} return h; } //minimum