图论教学中求最小生成树的方法研究

丁学利

摘  要：对图论教学中寻找最小生成树的常用三种算法进行论述，并结合实例对三种算法进行对比分析。同时指出在图论相关教学中应积极培养学生创新思考和多视角分析解决问题的能力。

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

中图分类号：O157.5         文献标识码：A           文章编号：1672-4437（2020）04-0039-04

树是一种特殊的图，在实际生活中应用广泛，如生成树、决策树、游戏树等。学界针对最小生成树的求法进行了深入研究和探讨，如Kruskal （克鲁斯克尔）于1956年最先给出了一种求最小生成树的算法，即避圈法[1];随后Prim（普里姆）于1957年給出了Prim算法[2];我国学者管梅谷于1975年给出了破圈法[3]等。在图论教材[4]中一般对避圈法进行了详细介绍，而对其它算法介绍较少。本文以《计算机数学》图论中寻找最小生成树的方法为切入点，结合实例深入探讨求最小生成树的三种算法。同时指出在教学中，即要系统详细地讲解基本概念，还要通过范例扩展学生的视野，从不同视角培养学生的发散思维和创新思维能力。

1 最小生成树[4]的概念

在一个连通图 中，称无圈的连通图为树，称包含图 全部顶点的树为图 的生成树。生成树上各边的权之和称为该生成树的权。连通图 的权最小的生成树称为图 的最小生成树。

根据上述定义，要确保如下两个方面：（1）在寻找权最小的边时，要保证不能出现回路;（2）若图 含有 个顶点，则寻找的 条边恰能将原图的所有顶点连通。

2 方法

2.1 避圈法

避圈法[1，5，6]是Kruskal于1956年提出的一种高效的寻找方法，即从图 的权值最小的边开始找，进行避圈式扩张，步骤如下：

（1）首先选取 中权值最小的边 （若有多个权最小的边，任选一个权最小的边），同时记该边 和其两个端点的图为 ;

（2）如果已选取边 ，那么再从 中选取边 ，使边 的权值最小且保证得到的 为无圈图。

（3）当图 的所有顶点都纳入到了 中，则停止，否则重复上述的第（2）步。

2.2 破圈法

破圈法[3，7]是我国学者管梅谷教授在Kruskal算法的基础上于1975年提出的一种算法。本算法的基本思想是逐步删除回路中权值最大的边，即先任选一个圈，删掉其中权值最大的一条边（如果权值最大的边不是一个，可任选一个），称为破圈，然后再查找下一个圈中权值最大的边并删除。这样不断破圈，直至删除图 中的所有圈为止，最后剩下的子图 即为所求。

2.3 Prim算法

Prim（普里姆）算法[2，8，9]的基本思路是通过逐个连接顶点的方法。一开始去掉所有的边，从任一顶点开始逐个连接，最终将所有顶点连接，算法结束。

Prim算法步骤如下：

（1）设置一个顶点集 和边集 。初始时，在 中任意取一个顶点 ，令 ，  ;

（2）选取与某个 邻接的顶点 ，使边 （顶点 与 相连的边）的权值最小，令 ， ;

（3）若所有的顶点都连接，则停止，否则重复第（2）步。

3 实例分析

某新建小区要铺设供水管道，其分布图如图1。图1中 （ ）表示每栋楼要接入供水管道的位置，连线上的数字表示它们之间的距离，试给出线路总长最短的铺设方案。

本题可看作是一个带权无向连通图 。怎样铺设才能使线路总长最短，其本质就是计算图1的最小生成树。下面分别利用避圈法、破圈法和Prim算法给出计算结果。

3.1 避圈法求解

避圈法的计算步骤如下：

（1）初始时，挑选最小边 ，用粗实线标识边 。记边集 ，得图2（a）。

（2）在余下的边中，有两个权值最小的边： 和 。任选一个，不妨选边 ，用粗实线标识边 。更新 ，得图2（b）。

（3）在剩余的边中寻找最小且无回路的边，权值最小的边是 ，用粗实线标识边 。更新 ，得图2（c）。

（4）在剩余的边中寻找，发现边 符合条件，用粗实线标识边 。更新 ，得图2（d）。

（5）继续在剩余的边中寻找，发现边 符合条件，用粗实线标识边 。更新 ，得图2（e）。

（6）继续在剩余的边中寻找，发现边 符合条件，用粗实线标识边 。更新 ，得图2（f）。

此时图 中包含了图 的所有顶点，算法结束。最短铺设方案如图2（f）中粗实线所示，其最短路线总长为26。

3.2 破圈法求解

破圈法求解步骤如下：

（1）任选一个圈，如圈 ，删掉其中权值最大的边 ，得图3（a）。

（2）再从余下的圈中任选一个，如圈 ，删掉其中权值最大的边 ，得图3（b）。

（3）再从余下的圈中任选一个，如圈 ，其中有两个边 和 的权值一样大，任选一个删除，如删除 ，得图3（c）。

（4）再从余下的圈中任选一个，如圈 ，删掉其中权值最大的边 ，得图3（d）。

（5）再从余下的圈中任选一个，如圈 ，删掉其中权值最大的边 ，得图3（e）。

（6）再从余下的圈 中，删掉权值最大的边 ，得图3（f）。

此时图3（f）中所有的圈都破掉了，算法结束。图3（f）即为所求。

3.3 Prim算法求解

用Prim算法求解过程如下：

（1）初始时，任选一个顶点，如选顶点 。定义新的 ， 。

（2）从 寻找与之连接的所有边，权值最小的边是 。更新 ， ，见图4（a）。

（3）从 中寻找与之连接的所有边，权值最小的边是 。更新 ， ，见图4（b）。

（3）从 中寻找与之连接的所有边，权值最小的边是 。更新 ， ，见图4（c）。

（4）从 中寻找与之连接的所有边，权值最小的边是 。更新 ， ，见图4（d）。

（5）从 中寻找与之连接的所有边，权值最小的边是 。更新 ， ，见图4（e）。

（6）从 中寻找与之连接的所有边，权值最小边是 。更新 ， ，见图4（f）。

此时访问了所有顶点，算法结束，图4（f）即为所求。

4 三种算法的比较[10，11]

避圈法的每一步都能得到最优解，因此它是一种精确求解算法。同时，该方法只是对图的边进行查找，这种算法的复杂度只与边数有关系，因此该方法较适合求解边稀疏的稀疏图。而当图的边数较多且规模较大时，其求解最小生成树的速度会变慢。

破圈法是从图 开始，通过逐步破除掉每个圈中最大的边，生成最小生成树。破圈法较适合直接在图上寻找最小生成树，当图的规模较大时，可安排若干个人对各个子图同时进行破圈，因此该方法很方便、实用。

Prim算法是从空图 开始，将顶点逐个连通的方式来寻找最小生成树的，因此Prim算法的复杂度只与顶点数有关，较适合边数较多的稠密图。但它是一种近似求解算法，实际应用时得到的不一定是最优解，因此求解时需注意。

破圈法和避圈法的本质是一样的，都是尽可能删掉权值大的边。Prim算法和避圈法本质都是贪心算法。避圈法需要先对权值排序后查找，但只需一次对权值排序后就可以找到最小生成树。虽然Prim算法是直接查找法，但需要多次对邻边排序才能找到，因此避圈法比Prim算法效率更高。

5 结束语

本文探讨了图论中寻找最小生成树常用的三种算法，并结合实例讨论了三种算法的优缺点。除了这三种算法之外，还有矩阵计算法[12]、逐步短接法[13]等。因此，在教学中，应以此类问题的研究和讨论为依托，从不同视角训练学生的发散思维，这样既有利于学生对概念和算法的深入理解，也有助于学生编程实现此算法。

参考文献：

[1]Kruskal J B. On the shortest spanning subtree of a graph and the traveling salesman problem[J]. Proceedings of the American Mathematical society， 1956，7（1）： 48-50.

[2]Prim R C. Shortest connection networks and some generalizations[J].The Bell System Technical Journal，1957，36（6）：1389-1401.

[3]管梅谷.求最小樹的破圈法数学的实践与认识[J].1975（4）：38-41.

[4]周忠荣.计算机数学[M].3版.北京：清华大学出版社，2014：191-193.

[5]王伟，孟思燕.Kruskal算法的研究与改进[J].重庆文理学院学报（自然科学版），2010，29（3）：25-27.

[6]孙凌宇，冷明，谭云兰，等.赋权有向图的最小生成树算法[J].计算机工程，2010，36（2）：61-63.

[7]闫超君.破圈法应用中的误区分析[J].河北工程大学学报（自然科学版），2012，29（2）：65-74.

[8]刘朝霞.改进的Prim算法在求解旅行商问题中的应用[J].阴山学刊，2015，29（1）：8-10.

[9]江波，张黎.基于Prim算法的最小生成树优化研究[J].计算机工程与设计， 2009，30（13）：3244-3247.

[10]张爱平，李强，陈志彬.最优树算法的教学研究[J].当代教育理论与实践，2013，5（10）：75-77.

[11]胥桂仙，骆宾杰，赵晨曦，等.离散数学实践教学探索[J].中央民族大学学报（自然科学版），2016，25（3）：61-67.

[12]毛华，史田敏，高瑞.求最小生成树的矩阵算法[J].郑州大学学报（理学版），2013，45（4）：23-25.

[13]张亚蕾.最大生成树算法及其应用的研究[J].河南教育学院学报（自然科学版），2019，28（2）：14-20.