稠密图的Prim 算法线性时间实现与研究

徐翠霞胥宗辉

（1.潍坊学院 计算机工程学院，山东 潍坊 261061；2.山东科技大学 计算科学与工程学院，山东黄岛 266590）

1 基本概念

1.1 完全图、稠密图和稀疏图

设G=(V,E)，V 是n 个顶点的非空有限集合，E 是m 条边的非空有限集合。不考虑顶点到其自身的边，则若G 是无向图，m 的取值范围是0 到n(n-1)/2；若G 是有向图，m 的取值范围是0 到n(n-1)。有n(n-1)/2 条边的无向图称为完全图，具有n(n-1)条弧的有向图称为有向完全图。当一个图有较少的边或弧，称它为稀疏图，反之为稠密图。

1.2 最小耗费生成树

设G =( V, E )是一个边上带权的连通无向图。若G 的一棵生成树( V, T )，有n 个顶点n-1 条边，且各边的权重之和为最小值，那么( V, T )这棵生成树就称为最小耗费生成树或简称最小生成树。

1.3 边界顶点、候选顶点、邻居

边(x,y)是一条这样的，如果两个顶点跨越两个集合，即顶点x ∈X，顶点y ∈Y，则称y 为边界顶点，也就是说y 是从Y 移向X 的候选顶点。设y 是一个边界顶点，那么至少存在一个顶点x ∈X 与之相邻接。

y 的邻居（记为N[y]）定义如下：是X 中具有以下性质的那个顶点x。在所有X 中与y 的邻接顶点中，边(x,y)的耗费c[x,y]最小。

设C[y]是连接y 和N[y]的边的耗费，即C[y]=c[y, N[y] ]。因此N[y]是X 中离y 最近的邻居。

1.4 堆及其基本运算

一个（二叉）堆是一棵完全二叉树，并且它的每个节点都满足以下特性：如果v 和p(v)分别是节点和它的父节点，那么存储在p(v)中的数据项键值不大于（或不小于）存储在v 中数据项的键值。这两种类型的堆，一般看做最小堆和最大堆，也可以看做小根堆和大根堆。

有n 个节点的堆T，可以由一个数组H[1..n]用下面的方式来表示：

● T 的根节点存储在H[1]中。

● 假设T 的结点x 存储在H[j]中，如果它有左子节点，这个子节点存储在H[2j]中；如果它有右子节点，这个子节点存储在H[2j+1]中。

● 元素H[j]的父节点如果不是根节点，则存储在H[j/2]

堆数据结构支持的运算有：

√ INSERT(H,x)，插入数据项x 到堆H 中。

√ DELETE(H,i)，从堆H 中删除第i 项。若H 为最小堆，DELETE(H,1)就从堆H 中删除最小键值的数据项。

√ DELETEMIN(H)，从一个非空的堆H 中删除最小键值的数据项并将数据项返回。

√ SIFTUP(H,H-1(x))，沿着从数据项x 到根节点的唯一一条路径，把x 上移到适合它的位置上，其中H-1(x)返回数据项x 在H 中的位置，这可以简单的用一个数组的第i 项来表示堆中顶点i 的位置来实现。

2 Prim 算法

2.1 算法的基本思想

算法可以从任意一个顶点开始构造最小生成树，如顶点1。设图G=(V,E)，为了简便起见，这里V 取整数集合｛1，2，...，n｝。算法开始时，建立两个顶点集合，分别是X=｛1｝和Y=｛2，3，...，n｝。接着构造一棵最小生成树，每次添加一条边。在每一步中，它找出一条权重最小的边(x,y)，这里x ∈X，y ∈Y。一方面把y 从Y 移动到X，另一方面把边(x,y)添加最小生成树边集之中。重复这一步直到Y 为空。

算法概括如下，它找出了最小生成树T 的边集。

输入：含权连通无向图G=(V,E)，V={1，2，...，n}

输出：由G 生成的最小生成树T 组成的边的集合。

STEP 1：T ←{}；X ←{1}；Y ←V-{1}；

STEP 2：初始化，置N[y]为1 并且对每个与1 相邻接的顶点y，令C[y]=c[1,y]。对每个与1 不相邻接的顶点y，置C[y]为∞。

for y ← 2 to n

if y 是1 的邻接顶点 then

N[y]← 1；C[y]←c[1,y]

else

C[y]←∞

end if

STEP 3：在每次迭代中，具有最小C[y]的顶点y 从Y 移到X。移动之后，Y 中每个与y 相邻接的顶点w 的N[w]和C[w]均予以更新

while Y ≠{}

i）设(x,y)是权重最小的边，其中x ∈X，y ∈Y

ii）X ←X ∪{y}；Y ←Y-{y}；T ←T ∪{(x,y)}

iii）for 每个邻接与y 的顶点w ∈Y

if c[ y, w ] ＜ C[ w ] then

N[w]← y；C[ w ]←c[ y, w ]

end if

end for

end while

2.2 算法的时间复杂度分析

对于具有n 个顶点、m 条边的连通无向图，算法第一阶段耗费时间为O(n)；算法第二阶段进行初始化，需要时间为O(n)；算法第三阶段耗费时间为O(n2+m)。这一阶段一共有三步，其中第一步搜索离X 最近的顶点y，每迭代一次需要时间为O(n)，因为算法对表示集合Y 的向量的每一项都要检查，而这一步执行了n-1次，所以这一步一共花费O(n2)。第二步将具有最小C[y]的顶点y 从Y 移到X，每迭代一次花费时间O(1)，总共花费时间O(n)。第三步是更新，最多执行m 次，这里m=|E|，这样这一步花费时间O(m)。

这就得到了算法的时间复杂性是O(n2+m) =O(n2) 。

3 改进的Prim 算法及其实现

3.1 算法设计技巧与实现方法

第一，算法输入的带权无向图用邻接表表示，边(x,y)的权重记为c[x,y]，存储在对应于x 的邻接表中y的节点中。

第二，X 和Y 两个集合，用布尔向量X[1..n] 和Y[1..n] 来实现。初始时只有顶点1 在X 中，即X[1]=1，Y[1]=0，并且对所有的i，若2 ≤i ≤n，则X[i]=0，Y[i]=1。这样，通过设置X[y]的值为1，来实现数学运算X ←X ∪{y}，并且设置Y[y]的值为0，来实现运算Y ←Y-{y}。

第三，用最小堆数据结构来保持边界顶点集，使得可以在O(logn)时间内取得Y 集中的顶点y，这个y和V-Y 集中一个顶点连接的边的耗费是最小的。

3.2 算法的基本思想

输入：含权连通无向图的邻接表。设G=(V,E)，V={1，2，...，n}。

输出：由G 生成的最小生成树T 组成的边的集合。假设已有一个空堆H。

STEP 1：T ←{}；X ←{1}；Y ←V-{1}；

STEP 2：for y ← 2 to n

if y 是1 的邻接顶点 then

N[y]← 1；C[y]←c[1,y]

INSERT(H,y) //将y 插入堆中

else

C[y]←∞

end if

STEP 3：for j ← 1 to n-1 //查找n-1 条边

i）y ← DELETEMIN(H) //删除最小堆的根节点

iii）for 每个邻接与y 的顶点w ∈Y

end for

3.3 算法的线性时间分析

开始的初始堆，只包含了与初始顶点1 相邻接的所有边界顶点，接下来在for 循环的每一次迭代中，首先选出堆中带有最小键值的顶点y 并删除，然后更新Y 中与y 邻接的每一个顶点w 的键值，接着，如果w 不在堆中，则将其插入；否则，如果w 有了更近的邻居，就需要将其在堆中上移到适当位置。

算法改进后的运行时间主要取决于堆运算。在算法中存在n-1 个DELETEMIN 运算，n-1 个INSERT运算和最多m-n+1 次的SIFTUP 运算，这些运算的每一个用二叉堆都需要O(logn)时间，因此就得到算法总共需要的时间是O(m logn)。

如果使用d 堆，运行时间可以改善如下，每次DELETEMIN 运算要花O( d log dn)时间，INSERT 运算或SIFTUP 运算需要O( log dn)时间，这样，总的运行时间是O( n d log dn+ m log dn)。如果选d =2+m/n，时间复杂性变成O( m log〔2+m/n〕n)。也就是说，如果是稠密图，对于某个ε＞0， m ≥n1+ε，那么算法的运行时间是：

=O(m/ε)

4 实例及堆的动态调整过程图示

4.1 最小生成树的生长过程

含权连通无向图G=(V,E)，V={1,2,3,4,5,6}。考虑图1(a)-图1(e)，虚线左边的顶点属于X，虚线右边的顶点属于Y。最小生成树的顶点用浅灰色突出显示，边用浅蓝色突出显示。注意，因为图中有权重相同的边，如(1,4)和(2,4)、(1,3)和(4,6)等，所以该图的最小生成树有多棵。若算法输入的邻接表顺序不同，得到的最小生成树也不同，但权重之和都是15。

图1 改进的Prim 算法构造最小生成树的过程

初 始 状 态 如 图1(a) 所 示， 这 里X={1}，Y={2,3,4,5,6}。从与顶点1 相关联的各条边中，找到一条权值最小的边(1,2)作为生成树上的第一条边，同时将顶点2 从Y 移动到X。这由移动虚线显示出来，现在顶点1 和2 均在虚线的左边。如图1(b)所示。

在图1(b) 中，X={1,2}, Y={3,4,5,6}。从Y 移动到X 的候选顶点为3 和4。因为在所有一端在X 一端在Y 的边中，边(1,4)和(2,4)的权值最小，4 从Y 移动到X。注意算法里保留4 的邻居是1，故加入最小生成树的边是(1,4)。如图1(c)所示。

接下来，在图1(c)中的三个候选顶点是3、5 和6。因为边(1,3)和(4,6)的权值最小，又因为算法用堆存储候选顶点，故这儿移动3 从Y 到X。然后，在图1(d)中的两个候选顶点是5 和6。因为边(3,6)的权值最小，那么移动6。最后，在图1(e)中的候选顶点只有一个5。因为边(5,6)的权值最小，那么移动5 从Y 到X。

每次从Y 向X 移动一个顶点y，它相对应的边就添加到T 中，而T 是最小生成树的边集，最终生成的最小生成树如图1(f)所示。

4.2 堆的创建及动态调整过程

在图1 中利用改进的Prim算法构造最小生成树时，初始状态为X={1}，Y={2,3,4,5,6}。先后从Y 向X 移动的顶点是{2 , 3 , 4, 6 , 5}，相对应的边添加到最小生成树的边集中。算法输出的5条边分别是{( 1 , 2 ) , ( 1 , 4 ) , ( 1, 3 ) , (3 , 6 ) , ( 6 , 5 )}。

初始堆如图2(a)所示，堆中的边界顶点是2、4 和3。删除堆根节点2，即将顶点2 从Y 移动到X，相应的边(1,2)添加到T中。这时，4 和3 的邻居不需要调整，如图2(b)所示。

图2 实例中堆的创建及调整

删除图2(b)中的堆根节点4，即将顶点4 从Y 移动到X，相应的边(1,4)添加到T 中，这时还需要插入两个新的边界顶点6 和5，如图2(c)所示。

删除图2(c)中的堆根节点3，即将顶点3 从Y 移动到X，相应的边(1,3)添加到T 中，这时X 中顶点5和6 的邻居由顶点4 调整为顶点3，如图2(d)所示。

删除图2(d)中的堆根节点6，即将顶点6 从Y 移动到X，相应的边(3,6)添加到T 中，这时X 中离顶点5 最近的邻居由顶点3 调整为顶点6，如图2(e)所示。

删除图2(e)中的堆根节点5，即将顶点5 从Y 移动到X，相应的边(6,5)添加到T 中，这时堆为空，算法结束如图2(f)所示。

5 结论

算法中使用的堆，其存储的数据项是用来候选的边界顶点。每个边界顶点包含两部分内容：一是顶点信息，二是相关联的边的权重。其中边的权重代表堆中数据项的键值。每次删除堆的根节点y，即把顶点y从Y 移动到X。Y 中每个与y 相邻的顶点w 的N[w]和C[w]均予以更新，若w 不在堆中，则插入它。否则，如果需要的话，根据修改后的C[w]，将w 在堆中上渗调整。

改进算法的实现代码已在VC++环境下运行通过，输入数据及输出数据完全正确。该算法的实现思路简单，具有较好的应用价值。