§7.4.2最小生成树(Minimum Spanning Tree) ■MST性质一大多数算法都利用了此性质 ■设G是连通图，G的生成树不唯一 设G=(N,E)是一连通图，U是V的真子集，若 (u,v)是所有连接U和V-U的边中权最小的边 ■MST:权最小的生成树，树的权是各边上 轻边)，则一定存在G的一棵最小生成树包括此 的权值之和 边 ·应用 P:设G的任何一棵最小生成树均不包括u,V: ◆n个城市之间的通信网，可构建n(n-1)/2条线路 ◆n个城市连通至少要n-1条线路，G的生成树是 1个可行的方案 最小生成树是最经济的可行方案 构造MST: 1、Prim算法 就是找轻边扩充到当前生成的树打=(U,TE)中 ■特点 ◆U一红点集、红边桌，的成 。当前形成的集合T=(U,TE)始终是一棵树 VU一白点集、白边集 。T中的顶点和边均为红色 ◆戴边集一连接红点和白点的边 ◆轻边一权量轻的素边，或最短紫边（若权为长度）（山，V) ■基本思想（贪心法） ◆设V(G={0,1,n-1} 算法的每一步均是在连接红、白点集的紫 边中选一轻边扩充到T(贪心)，T从任意 一点r开始(r为根)，直至U=V为止。 MST性质保证了贪心选择策略的正确性。 . 1、Prim算法 1、 Prim算法 ■如何找轻边？ ■如何维护候选轻边集？ 冬可能的款边集 当把轻边(，v)扩充至T中时， 设红点集U=k,白点集V-U=n-k,则可能的紫边 数为：knk小： v由白点变为红点，紫边(u,v)变为红边： 在此戴边集中选择轻边效率太低。 对每个剩余白点j,边(，j)由白变紫，此 ◆构造候选轻边巢 新紫边的长度可能小于白点原来所关联的最短 构造较小的紫边集，但保证轻边在其中。 紫边。 因为，Vy∈自点集，从y到各红点的紫边中，只 须调整候选轻边集，用更短的新紫边(V,) 有最短的那一条才可能是轻边，所以只须保留所有 一k个白点所关联的最短薰边作为轻边候选集即可。 取代原来关联于的最短紫边。 显然，轻边是该候选集中权量轻的边。 可以针对红点集来构造候选轻边集吗？ 11 1 §7.4.2 最小生成树（ Minimum Spanning Tree） „设G是连通图，G的生成树不唯一 „MST：权最小的生成树，树的权是各边上 的权值之和 „应用 ™n个城市之间的通信网，可构建n(n-1)/2条线路 ™n个城市连通至少要n-1条线路，G的生成树是 1个可行的方案 ™最小生成树是最经济的可行方案 2 „MST性质－大多数算法都利用了此性质 设G＝(V，E)是一连通图，U是V的真子集，若 （u，v）是所有连接U和V-U的边中权最小的边 （轻边），则一定存在G的一棵最小生成树包括此 边。 Pf：设G的任何一棵最小生成树均不包括(u，v)； T’ u v u’ v’ u v u’ v’ T U U V-U V-U 3 „构造MST： 就是找轻边扩充到当前生成的树T＝（U，TE）中 ™U－红点集、红边集，构成T ™V-U－白点集、白边集 ™紫边集－连接红点和白点的边 ™轻边－权最轻的紫边，或最短紫边(若权为长度):（u1，v1） u1 v1 U V-U 5 50 15 u 23 2 u3 v2 v3 4 1、Prim算法 „特点 ™当前形成的集合T＝（U，TE）始终是一棵树 ™T中的顶点和边均为红色 „基本思想（贪心法） ™设V(G)={0,1,…,n-1} ™算法的每一步均是在连接红、白点集的紫 边中选一轻边扩充到T（贪心），T从任意 一点r开始（r为根），直至U＝V为止。 MST性质保证了贪心选择策略的正确性。 5 1、Prim算法 „ 如何找轻边？ ™可能的紫边集 设红点集|U|=k, 白点集|V-U|=n-k，则可能的紫边 数为：k(n-k)。 在此紫边集中选择轻边效率太低。 ™构造候选轻边集 构造较小的紫边集，但保证轻边在其中。 因为，∀v∈白点集，从v到各红点的紫边中，只 有最短的那一条才可能是轻边，所以只须保留所有n －k个白点所关联的最短紫边作为轻边候选集即可。 显然，轻边是该候选集中权最轻的边。 可以针对红点集来构造候选轻边集吗？ 6 1、Prim算法 „如何维护候选轻边集？ 当把轻边（u，v）扩充至T中时， v由白点变为红点，紫边（u，v）变为红边； ∵对每个剩余白点j，边（v，j）由白变紫，此 新紫边的长度可能小于白点j原来所关联的最短 紫边。 ∴须调整候选轻边集，用更短的新紫边（v，j） 取代原来关联于j的最短紫边