最小生成树三种求解方法的分析与实现
作者：李龙霞 陈燕 于晓倩
来源：《电脑知识与技术》2021年第33期
        摘要：圖作为一种典型的非线性结构，用图来描述问题简明直观。而最小生成树作为图的重要应用之一，用于解决优化路线，如何使网络通信线路成本最低，电话线路最短等问题。将此类问题转化为最小生成树问题进行求解。最小生成树是所有生成树中代价最小的生成树。它以邻接矩阵的方式存储，采用Prim算法，Kruskal算法和破圈法的方法进行求解。
        关键词：图;最小生成树;Prim算法;Kruskal算法;破圈法
        中图分类号：TP301.6;TP311.12 文献标识码：A
        文章编号：1009-3044（2021）33-0044-03
        开放科学（资源服务）标识码（OSID）：
weight的几种形式        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），两个城市要铺
设宽带的路线用一条边表示，铺设宽带线路的成本用边上的权值表示。使总的成本最低的过程，就是求解最小生成树的过程。以此为例说明三种求最小生成树的方法：