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

基于Sollin算法的最小生成树求解
计算机光盘软件与应用
Computer CD Software and Applications工程技术2012 年第 15 期
基于 Sollin 算法的最小生成树求解
陈海珠，郑卉
401重要性质: 性质 1:设 G=(V， E)是一个带权连通图，U 是 V 的一 个非空子集。若 u?U，v?V-U，且(u， v)是 U 中顶点到 V-U step0中顶点之间权值最小的边，则必存在一棵包含边(u， v)的最
小生成树。 当一条边(u， v)加入 T 时，必须保证 T?{(u， v)}仍是 MST 的子集，我们将这样的边称为 T 的安全边。基于性质 1， 构建 MST 的一般算法可描述为:针对图 G，从空树 T 开始， 往集合 T 中逐条选择并加入 n-1 条安全边(u， v)，最终生成 一棵含 n-1 条边的 MST。构造最小生成树的算法有许多种， step1step2典型的构造算法有 Prim(普里姆)算法、Kruskal(克鲁斯卡尔) 图 1 用 Sollin 算法构造最小生成树的过程算法和 Sollin 算法。这三个算法均是对前述一般算法的进一
步细化，它们的区别仅在于求安全边的方法不同。Prim 和 3 Sollin 算法的实现
Kruskal 在本专科数据结构课程中有详细的介绍，而 Sollin 算
与 Kruskal 算法类似，在实现 Sollin 算法是也需要用一个 法涉及较少。本文基于边集数组这一存储结构，详细说明
一维数组 tset 存放 G 中各顶点所处的树的编号。开始时令 Sollin 算法的步骤与实现。 tset[i]=i，即图中每个顶点自成一棵树，树的编号简单地设置
为该顶点在图中的位置。在寻找各棵树连向其他树的权值最
小边(i， j)时，若 tset[i]=tset[j]，则表明 v和 v处在同一棵树 i j
中;tset[i]?tset[j]，此时在判断其权值是否是最小的。找到这
样的边后，将此边加入 Te，并将这两棵树合并，合并方法是
将其中一棵树的编号换成另一棵树的编号。 2 Sollin 算法
计算机光盘软件与应用
Computer CD Software and Applications2012 年第 15 期工程技术
} 以下给出 Sollin 算法的具体描述，其中，图的存储结构
i=0; 采用边集数组，其定义如下所示: while(closet[i]!=INFINITY) /*实现树的合并*/ typedef struct ENode{ int vex1，vex2; /*该边依附的两个顶点在图中的位置*/ {
WeightType w; /*与边相关的信息(如权值)*/ v1=G->edgelist[edge[i]].vex1;
}ENode; v2=G->edgelist[edge[i]].vex2;
t1=tset[v1]; t2=tset[v2]; typedef struct {
int vexnum， edgenum; /*图的当前顶点数和边数*/ if(t1!=t2)
{ VexType vexlist[MAX_EDGE_NUM] T[s].vex1= v1; T[s].vex2