曲大鹏，侯振桓，宣伟宏，宋宝燕

(辽宁大学 信息学院，辽宁 沈阳 110036)

0 引言

一个连通图的生成树是图的极小连通子图，它包含图中的所有顶点，并且只包含保持图连通的最少的边.若去掉它的一条边，就会使生成树变成非连通图，若增加它的一条边，就会在图中形成一条回路.对于一个无向带权连通图G=(V，E)，生成树不同，每棵树的权(即树中所有边的权值之和)也可能不同.设K为G的所有生成树的集合，若T为K中的权值最小的那棵，则T称为G的最小生成树(Minimum Spanning Tree，MST)[1].

最小生成树具有以下性质：

1)最小生成树不是唯一的.

2)最小生成树的边的权值之和是唯一的.

3)最小生成树的边数为顶点数减1.

1 最小生成树算法

最小生成树常用的算法有普里姆Prim算法和克鲁斯卡尔Kruskal算法[2，3].为方便分析，我们设定一个无向带权连通图G=(V，E)，V为其顶点集合，E为边集合.

1.1 Prim算法

Prim算法是维护一个在最小生成树中的点的集合，从某个起始点出发，不断选择并添加离集合最近的点，直到覆盖所有要加入的点.

Input：G.

Output：MST(Vnew，Enew).

1)初始化：Vnew={x}，其中x为集合V中的任一节点(起始点)，Enew={}，为空；

2)重复下列操作，直到Vnew=V：

a.在集合E中选取权值最小的边，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V(如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一)；

b.将v加入集合Vnew中，将边加入集合Enew中；

3).输出：使用集合Vnew和Enew来描述所得到的最小生成树.

接下来用一个简单示例来演示Prim算法，如图1所示.

Step 1：初始u={A}，v={B，C，D，E，F}，选择权值最小的边，并将C加入u集合；

Step 2：u={A，C}，v={B，D，E，F}，选择权值最小的边，并将F加入到u集合；……