设T为所选择的边的集合，初始化T=

设T V为已在树中的顶点的集合，置T V= { 1 }

令E为网络中边的集合

w h i l e(E< > ) & & (| T | < > n-1) {

令（u , v）为最小代价边，其中u T V, v T V

i f（没有这种边） b re a k

E=E- { (u,v) } / /从E中删除此边

在T中加入边（ u , v）

}

if (| T | = =n- 1 ) T是一棵最小生成树

else 网络是不连通的，没有最小生成树

图13-14 Prim最小生成树算法

如果根据每个不在T V中的顶点v 选择一个顶点n e ar (v)，使得n e ar (v) ? TV 且c o st (v, n e ar (v) )的值是所有这样的n e ar (v) 节点中最小的，则实现P r i m算法的时间复杂性为O (n2 )。下一条添加到T中的边是这样的边：其cost (v, near (v)) 最小，且v T V。

3. Sollin算法

S o l l i n算法每步选择若干条边。在每步开始时，所选择的边及图中的n个顶点形成一个生成树的森林。在每一步中为森林中的每棵树选择一条边，这条边刚好有一个顶点在树中且边的代价最小。将所选择的边加入要创建的生成树中。注意一个森林中的两棵树可选择同一条边，因此必须多次复制同一条边。当有多条边具有相同的耗费时，两棵树可选择与它们相连的不同的边，在这种情况下，必须丢弃其中的一条边。开始时，所选择的边的集合为空。若某一步结束时仅剩下一棵树或没有剩余的边可供选择时算法终止。

图1 - 6给出了初始状态为图1-12a 时，使用S o l l i n算法的步骤。初始入选边数为0时的情形如图13-12a 时,森林中的每棵树均是单个顶点。顶点1，2，.，7所选择的边分别是(1.6), (2,7),(3,4), (4,3), (5,4), (6,1), (7,2)，其中不同的边是( 1 , 6 )，( 2 , 7 )，(3,4) 和( 5 , 4 )，将这些边加入入选边的集合后所得到的结果如图1 3 - 1 6 a所示。下一步具有顶点集{ 1 , 6 }的树选择边( 6 , 5 )，剩下的两棵树选择边( 2 , 3 )，加入这两条边后已形成一棵生成树，构建好的生成树见图1 3 - 6 b。S o l l i n算法的C + +程序实现及其正确性证明留作练习（练习3 2 )。

此新闻共有8页  第 1  2  3  4  5  6  7  8 页