Tree),常简称为最小生成树(记为MST)。最小生成树问题就是给定G,找出G的一个最 小生成树T的问题。 本节将介绍用于求解MST问题的 Sollin算法,并将其实现。 141最小生成树串行算法 Sollin算法 (Sollin Algorithm)是众多用于求解MST问题的算法之一,其原理为:算法开 始时,图中的N个顶点视为一片森林,每个顶点视为一棵树:算法主循环的流程中,森林 里每棵树同时决定其连向其它树的最小邻边,并将这些边加入森林中,实现树的合并:循环 到森林中只剩一棵树时终止。由于森林中树的数目每次至少减少一半,所以只要lgN次循 环就可以找出MST。 算法中以D(i)为顶点i所在的树的编号,edge(i)和 closet(i)为树i连向其它树的最小邻 边和其长度,则 Sollin算法的形式描述见算法15.6,其时间复杂度为O(N2begN)。 算法156 Sollin mst算法 输入:无向图G的边权矩阵W 输出:G的最小生成树的边集合T procedure Sollin-MST /*以下所有顶点初始化为一棵孤立的树* (1)for i=0 to N-l do (1) endfor (2)T初始化为空集 3)while T<N-1 do /*以下为各树寻找连向其它树的最小边权* (3.1)for每棵树ido closet()=∝ endfor (32)for图G中每条边(v,u)do if D(v)*D(u) and w(v, u)<closet(D(v))then (i)closet(D(v))=w(v,u) endif endfor /*以下是树的合并* (33)for每棵树ido (i)ifD(v)≠Du)then T=T+{(v,u)} 树D(v)和D(u合并 endor endwhileTree），常简称为最小生成树（记为 MST）。最小生成树问题就是给定 G，找出 G 的一个最 小生成树 T 的问题。 本节将介绍用于求解 MST 问题的 Sollin 算法，并将其实现。 1.4.1 最小生成树串行算法 Sollin 算法(Sollin Algorithm)是众多用于求解 MST 问题的算法之一，其原理为：算法开 始时，图中的 N 个顶点视为一片森林，每个顶点视为一棵树；算法主循环的流程中，森林 里每棵树同时决定其连向其它树的最小邻边，并将这些边加入森林中，实现树的合并；循环 到森林中只剩一棵树时终止。由于森林中树的数目每次至少减少一半，所以只要㏒ N 次循 环就可以找出 MST。 算法中以 D(i)为顶点 i 所在的树的编号， edge(i) 和 closet(i)为树 i 连向其它树的最小邻 边和其长度，则 Sollin 算法的形式描述见算法 15.6，其时间复杂度为 O(N2 ㏒ N)。 算法 15.6 Sollin MST 算法 输入：无向图 G 的边权矩阵 W 输出：G 的最小生成树的边集合 T procedure Sollin-MST Begin /* 以下所有顶点初始化为一棵孤立的树 */ (1) for i=0 to N-1 do D(i) = i endfor (2) T 初始化为空集 (3) while |T| < N-1 do /* 以下为各树寻找连向其它树的最小边权 */ (3.1) for 每棵树 i do closet(i) = ∞ endfor (3.2) for 图 G 中每条边(v,u) do if D(v)≠D(u) and w(v,u)<closet(D(v)) then (ⅰ) closet(D(v)) = w(v,u) (ⅱ) edge(D(v)) = (v,u) endif endfor /* 以下是树的合并 */ (3.3) for 每棵树 i do (ⅰ) (v,u) ← edge(i) (ⅱ) if D(v)≠D(u) then T = T + { (v,u) } 树 D(v)和 D(u)合并 endif endfor endwhile End