、最小生成树性质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