李龙霞 陈燕 于晓倩

摘要：图作为一种典型的非线性结构，用图来描述问题简明直观。而最小生成树作为图的重要应用之一，用于解决优化路线，如何使网络通信线路成本最低，电话线路最短等问题。将此类问题转化为最小生成树问题进行求解。最小生成树是所有生成树中代价最小的生成树。它以邻接矩阵的方式存储，采用Prim算法，Kruskal算法和破圈法的方法进行求解。

关键词：图;最小生成树;Prim算法;Kruskal算法;破圈法

中图分类号：TP301.6;TP311.12   文献标识码：A

文章编号：1009-3044（2021）33-0044-03

开放科学（资源服务）标识码（OSID）：

Analysis and Realization of Three Methods of Solving Minimum Spanning Tree

LI Long-xia， CHEN Yan， YU Xiao-qian

（School of Maritime Economics and Management， Dalian Maritime University， Dalian 116026， China）

Abstract： Graph， as a typical nonlinear structure， is simple and intuitive to describe the problem. As one of the most important applications of graphs， the minimum spanning tree is used to solve the problems of optimizing routes， minimizing the cost of network communication lines and the shortest telephone lines. This kind of problem is transformed into the minimum spanning tree problem to solve. The minimum spanning tree is the spanning tree with the least cost among all spanning trees. It is stored in the form of adjacency matrix and solved by Prim algorithm， Kruskal algorithm and loop breaking method.

Key words： Graph; Minimum Spanning Tree; Prim algorithm; Kruskal algorithm; Broken Ring Method

1 引言

求解最小生成树是解决工程类问题的一种重要手段。许多工程类问题（如城市公交，油管铺设等）中，涉及n个城市，m条道路的选择。而这些道路彼此交互，用图来描述问题更为直观明晰。若在一个图中，任意两个顶点之间都存在一条路径，则称此图为连通图。若某个连通图有n个顶点和e条边，那么由n个顶点，n-1条边构成的是极小连通图，也称为该连通图的生成树。在实际问题中，往往需要得到成本最低、造价最小的最小生成树。如利用最小生成树来解决工程类问题中的网络线缆问题，将网络线缆问题中的通信网络城市看作图中的顶点，城市间铺设的电缆线路看作图中顶点之间的边，城市之间所修建的电缆线路的代价看作时图中各边上的权值。这样就把网络线缆问题转换成了求一个连通网的最小生成树问题。

求解最小生成树有两大类解法，即避圈法和破圈法。避圈法的做法是：利用MST性质（假设N=（V，{E}）是一个连通网，U是顶点V的一个非空子集。若（u，v）是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边（u，v）的最小生成树。），避免形成回路，介绍两种不同的算法——Prim算法和Kruskal算法。破圈法的做法是：去掉图中圈的权值最大的边，破掉回路。破圈法的算法是从图G的任意圈开始，去掉该圈中权值最大的一条边，称为破圈，不断破圈，直到图G中没有圈为止。

2 求解最小生成树

例如：现需要在南京、合肥、南昌、杭州、武汉、福州和长沙七个城市之间铺设宽带，每个城市用一个顶点表示（这七个城市表示为顶点A，顶点B，...，顶点G），两个城市要铺设宽带的路线用一条边表示，铺设宽带线路的成本用边上的权值表示。使总的成本最低的过程，就是求解最小生成树的过程。以此为例说明三种求最小生成树的方法：

2.1 Prim算法

Prim算法是由美国科学家罗伯特·普里姆（Robert C. Prim）独立发现。

Prim算法的思想是：假设G连通，V为G上顶点的集合，E为G上边的集合，U是G最小生成树中顶点的集合，TE是G最小生成树中边的集合。算法初始状态为U={u0}，TE={}，不断从所有满足（u，v）∈E（u∈U，v∈V-U）的边中找出权值最小的边（u0，v0），若（u0，v0）与TE中的边不构成回路，则将（u0，v0）并入集合TE中，同时v0并入U，直到V=U为止。Prim算法的核心：始终保持TE中的边集构成一棵生成树。

核心算法：

// 从未加入到最小生成樹的顶点中找出权值最小的顶点。

while （j < G.vexnumber） {

// 若weights[j]=0，意味着第j个节点已经加入最小生成树

if （res[j].weight ！= 0 && res[j].weight < min）{

min = res[j].weight;

k = j;

}

j++;

}

//在未加入最小生成树的顶点中，第k个是权值最小的顶点

//将第k个顶点加入最小生成树的结果数组中

prims[index++] = G.vex[k];

算法说明：

1）图的存储方式有邻接矩阵、邻接表、十字链表等，但由于邻接矩阵能更清晰地显示出点与点之间有无边以及权值的大小，故在上面的算法中是以邻接矩阵的方式存储。例题中的图1表示为如图2的邻接矩阵。

邻接矩阵的存储结构

typedef struct _graph

{ char vex[MAX];       // 顶点集合

int vexnumber，edgnumber;  // 顶点数和边数

int matrix[MAX][MAX]; // 邻接矩阵

}Graph， *PGraph;

2）借助prims数组来记录顶点，res数组来记录边的权值（包括两个顶点和权值）。（注：res[].begin和res[].end并不代表该边的起点和终点，只是为了将该边连接的两个顶点区分开。）

3）res数组记录的不是结果，而是过程。第k个顶点要加入U中，则res[k].weight置为0;若在这一次循环中，第k个顶点未被加入到U中，则res[k]的值都要更新，res[k].weight更新为一个顶点在U中，另一个顶点在V中的边的权值。

以图1为例，假设起点为A，那么U为{A}，TE={}，V={B，C，D，E，F，G}。表1中列出了Prim算法详细的求解过程。

Prim算法是从顶点出发，在已加入的顶点出发的边中选择权值最小的边。Prim算法的时间复杂度为O（n^2），其时间复杂度与顶点的数目有关，与边的数目无关，因此更适合于求稠密图的最小生成树。

2.2 Kruskal算法

Kruskal算法是由Joseph Bernard Kruskal Jr.提出。算法步骤是：假设G是连通的且包含n个顶点，先构造一个只含n个顶点的子图T。1）遍历图G，找出权值最小的边。2）若将此条边加入T中不形成回路，则加入最小生成树T中;若将此条边加入T中形成回路，则舍弃这条边，继续步骤1;直到子图T中含n-1条边为止，算法结束。此时得到的子图T就是图G的最小生成树。仍以图1为例，假设子图T包含所有点，不含边，具体步骤见表2。

说明：（A，D）和（C，E）权值相等，任选其一加入T即可，加入的顺序并不影响最终结果。（A，B）和（B，E）同理。

Kruskal算法是从所有未加入边集中选择权值最小的边，并把它的顶点加入顶点集。Kruskal算法的时间复杂度为O（eloge）（e为网中边数），只与边相关，因此更适合于求稀疏图的最小生成树。

2.3 破圈法

破圈法是由我国著名数学家管梅谷在1975年提出。破圈法是区别于避圈法（Prim算法和Kruskal算法）的一种寻找最小生成树的算法。破圈法是"见圈破圈"，即如果看到图中有一个圈，就将这个圈的边去掉一条，直至图中再无一圈为止。步骤如下：①在图中找一个回路，去掉该回路中权值最大的边，但要保持图仍为连通。②反复①过程，直至图中再无回路（但仍保持连通），得到最小生成树。

仍然以图1为例，按照路径长度从小到大进行查找，以避免无序。求解过程如表3。

此时，图中已无圈，且有（顶点数-1）条边。

最小生成树的总代价=5（A，D）+7（A，B）+6（D，F）+7（B，E）+5（C，E）+9（E，G）=39

3 结论

这三个算法都是基于贪婪算法的思想设计的（一个从任意点开始，一个从最小边开始，一个从任意圈开始），每一步选择局部最优，从而期望得到全局最优的算法。Prim算法是对节点进行遍历，时间复杂度是平方阶，只与点的个数有关，因此更适合于求稠密图的最小生成树。Kruskal算法是对边进行遍历，时间复杂度是对数阶，只与边的数目有关，因此更适合于求稀疏图的最小生成树。破圈法算法是对每个回路进行破坏。

这三个算法中，Prim算法和Kruskal算法是在数据结构课程中学习，而破圈法是在管理运筹学课程中学习，是从形成回路的边中找到权值最大的边删除，此方法较为简单。在学习过程中要善于总结，将不同学科中解決相同问题的不同方法放在一起去学习、比较。这样，解决实际问题的时候，才能根据具体问题的特点选择更合适的方法。

参考文献：

[1] 陈燕，曹妍，贾红雨，李晔.数据结构[M].北京：科学出版社，2016.

[2] 严蔚敏，李冬梅，吴伟民.数据结构：C语言版[M].2版.北京：人民邮电出版社，2015.

[3] 张淑萍.最小生成树算法及其在天然气管道网中的应用研究[J].电脑知识与技术，2020，16（17）：214-216.

[4] 张恒，孙建春，涂鹏，等.利用通风网络数据结构构造最小生成树的方法[J].地下空间与工程学报，2018，14（S2）：887-892.

[5] 杨晶，张兆鑫，王鹏.最小生成树算法在城市基础建设中的应用[J].电子测试，2015（2）：37-38，36.

[6] 王化宇.最小生成树算法及其应用[J].内蒙古科技与经济，2011（6）：72-73.

[7] 段东东.最小生成树算法及其应用[J].西安航空技术高等专科学校学报，2010，28（1）：55-57.

[8] 王新奇.最小生成树算法及其应用[J].西安文理学院学报（自然科学版），2009，12（3）：23-26.

【通联编辑：梁书】