基于Sollin算法的最小生成树求解

Prim算法、Kruskal算法和Sollin算法是最小生成树的典型构造算法。这三个算法均基于贪婪策略。Prim和Kruskal算法在本专科数据结构课程中有详细的介绍,而SoUin算法涉及较少。本文基于边集数组这一存储结构,详细说明了somn算法的步骤与实现。

I L班千 f司 1/. 异兀人l十 2. m

工程技术

C m u e D S fw r n p lc t o s o p tr C o t a e a dA p i a i n

2 1年第 l 02 5期

基于 S In o 算法的最小生成树求解 li 陈海珠，郑卉 (重庆电子工程职业学院，重庆4 13 ) 0 3 1

摘要： r算法、 r kl Pm i K u a算法和 Sl算法是最小生成树的典型构造算法。 s oi l n这三个算法均基于贪婪策略。 r Pi m和 K sa m kl 算法在本专科数据结构课程中有详细的介绍，而 SUn算法涉及较少。本文基于边集数组这一存储结构，详细说明了 s mn算 oi o法的步骤与实现。

关键词：Sln算法；最小生成树；图；数据结构 ol i

’ 中图分类号：T 31 文献标识码：A文章编号：10— 59 21)5 09— 2 P0. 6 07 99 ( 2 1— 02 0 0对连通图 G{= V, E, T T, T}}令={v e为其最小生成树。 用 S ln算法构造最小生成树的步骤为： ol i 在一个具有 n个顶点的连通图 G中，如果存在子图

1引言

( )令图中每个顶点表示一棵树，原图构成一个森林 1S,即 T= T v V, T= e O;

G含 G中所有顶点和一部分边，且不形成回路，则包称 G图 G的生成树。如果连通图是一个带权图，为那么其生成树中的边也带权，将生成树中所有边的权值之和称为该

() 2每棵树同时决定其连向其他树的最小权值邻边，并

将这些边加入森林 S T中，实现树的合并，j司时将这些边也加入 T,注意一个森林中的两棵树可选择同一条边，因此必须 e多次复制同一条边；

生成树的代价，则代价最小的生成树称为最小代价生成树( mmu C sS ann re简称 MS )简称最小生成树。 Mi m ot pn igTe, T, 许多应用问题都是一个求连通图的最小生成树问

( )重复步骤 ( ) 3 2,直到 S T中只剩一棵树为止。图 1出了用 S ln算法构造最小生成树的过程。给 ol i

题。例如：要在 n个城市之间铺设光缆，主要目标是要使这 n个城市的任意两个之间都可以通信；铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，故另一

⑤

①④

个目标是要使铺设光缆的总费用最低。这就需要找到

⑤④

这个光缆铺设图的最小生成树。 对于最小生成树，有以下重要性质：

⑤

性质 1:设 G v, E是一个带权连通图，u是 v的一 )个非空子集。若 u EU,￣V U,且(, v -“ 是 u中顶点到 v u -

中顶点之间权值最小的边，则必存在一棵包含边(, v的最“ ) 小生成树。 当一条边(, v加入 T时，必须保证 Tu{,“ ) (“}仍是

MS T的子集，我们将这样的边称为 T的安全边。基于性质 1,

构建 MS T的一般算法可描述为：针对图 G,从空树 T开始，往集合 T中逐条选择并加入，1 1条安全边(, v,最终生成 .“ )一

s ep1 t

st p2 e

图 1用 s l i o ln算法构造最小生成树的过程

棵含，1条边的 MS。构造最小生成树的算法有许多种， 1 . T

3 S n算法的实现 oI li与 K uk l rsa算法类似，实现 S ln法是也需要用一个在 ol算 i一

典型的构造算法有 P (里姆 )血n普算法、K uk l rsa克鲁斯卡尔) (

算法和 S ln算法。这三个算法均是对前述一般算法的进一 ol i步细化，它们的区别仅在于求安全边的方法不同。Pi和 r m K uk l r sa在本专科数据结构课程中有详细的介绍，而 S ln算 ol i

维数组 t t存放 G中各顶点所处的树的编号。开始时令 s e

t t]i s[=,即图中每个顶点自成一棵树，树的编号简单地设置 ei为该顶点在图中的位置。在寻找各棵树连向其他树的权值最小边(,力时，若 t t]t t] f s[=s[,则表明 v和 v处在同一棵树 ei e/ f j

法涉及较少。本文基于边集数组这一存储结构，详细说明 S ln算法的步骤与实现。 ol i

中；t t] st] s[Cte],此时在判断其权值是否是最小的。找到这 ei[样的边后，将此边加入 T,并将这两棵树合并，合并方法是 e将其中一棵树的编号换成另一棵树的编号。

2 S i o ln算法 l