最小生成树问题

type

status

date

slug

summary

最小生成树

生成树

树是图论中的基本概念。连通的无圈图称为树（Tree），就是不包含循环的回路的连通图。

对于无向连通图，如下图所示，生成树（Spanning tree）是原图的极小连通子图，它包含原图中的所有个顶点，并且有保持图连通的最少的边，即只有足以构成一棵树的条边。

生成树满足：（1）包含连通图中所有的顶点；（2）任意两顶点之间有且仅有一条通路。因此，生成树中边的数量 = 顶点数 - 1。

对于非连通无向图，遍历每个连通分量中的顶点集合所经过的边是多颗生成树，这些连通分量的生成树构成非连通图的生成森林。

最小生成树和最大生成树

遍历连通图的方式通常有很多种，也就是说一张连通图可能有多种不同的生成树

无向赋权图的生成树中，各条边的权重之和最小的生成树，称为最小生成树（minimum spanning tree，MST），也称最小权重生成树

对应地，各条边的权重之和最大的生成树，称为最大生成树（maximum spanning tree）

最小生成树（MST）是图论中的基本问题，具有广泛的实际应用，在数学建模中也经常出现。

例如，在若干城市之间铺设通信线路，使任意两个城市之间都可以通信，要使铺设线路的总费用最低，就需要找到最小生成树。类似地，路线设计、道路规划、官网布局、公交路线、网络设计，都可以转化为最小生成树问题，如要求总线路长度最短、材料最少、成本最低、耗时最小等。

在实际应用中，不仅要考虑网络连通，还要考虑连通网络的质量和效率，就形成了带有约束条件的最小生成树：

直径限制最小生成树（Bounded diameter minimum spanning tree）：对给定的连通图，满足直径限制的生成树中，具有最小权的树，称为直径限制最小生成树。直径限制最小生成树问题在资源优化问题中应用广泛，如网络设计的网络直径影响到网络的传输速度、效率和能耗。

度限制最小生成树（Degree constrained minimum spanning tree）：对给定的连通图，满足某个节点或全部节点的度约束（如入度不超过 k）的生成树中，具有最小权的树，称为度限制最小生成树。实际应用中，为了控制节点故障对整个系统的影响，需要对节点的度进行限制。

最小生成树算法

构造最小生成树的算法很多，通常是从空树开始，按照贪心法逐步选择并加入条安全边（不产生回路），最终得到最小生成树

最小生成树的典型算法有普里姆算法（Prim算法）和克鲁斯卡算法（Kruskal算法）

普里姆算法（Prim算法）

Prim 算法以顶点为基础构造最小生成树，每个顶点只与连通图连接一次，因此不用考虑在加入顶点的过程中是否会形成回路。

算法从某一个顶点 s 开始，每次选择剩余的代价最小的边所对应的顶点，加入到最小生成树的顶点集合中，逐步扩充直到包含整个连通网的所有顶点，可以称为“加点法”。

Prim 算法中图的存贮结构采用邻接矩阵，使用一个顶点集合 u 构造最小生成树。由于不断向集合u中加点，还需要建立一个辅助数组来同步更新最小代价边的信息。

Prim 算法每次选择顶点时，都需要进行排序，但每次都只需要对一部分边进行排序。Prim 算法的时间复杂度为，与边的数量无关，适用于边很多的稠密图。

采用堆实现优先队列来维护最小点，可以将Prim算法的时间复杂度降低到，称为Prim_heap 算法，但该算法的空间消耗很大。

克鲁斯卡算法（Kruskal算法）

Kruskal 算法以边为基础构造最小生成树，利用避圈思想，每次找到不使图构成回路的代价最小的边。

算法初始边数为 0，每次选择一条满足条件的最小代价边，加入到边集合中，逐步扩充直到包含整个生成树，可以称为“加边法”。

Kruskal 算法中图的存贮结构采用边集数组，权值相等的边在数组中的排列次序是任意的。Kruskal算法开始就要对所有的边进行排序，之后还需要对所有边应用 Union-Find算法，但不再需要排序。

Kruskal 算法的时间复杂度为，主要是对边排序的时间复杂度，适用于边较少的稀疏图。

NetworkX 的最小生成树算法

NetworkX 的最小/最大生成树函数

函数	功能
minimum_spanning_tree(G[, weight,…])	计算无向图上的最小生成树
maximum_spanning_tree(G[, weight,…])	计算无向图上的最大生成树
minimum_spanning_edges(G[, algorithm,…])	计算无向加权图最小生成树的边
maximum_spanning_edges(G[, algorithm,…])	计算无向加权图最大生成树的边

minimum_spanning_tree() 使用

minimum_spanning_tree(G, weight=‘weight’, algorithm=‘kruskal’, ignore_nan=False)

minimum_spanning_edges(G, algorithm=‘kruskal’, weight=‘weight’, keys=True, data=True, ignore_nan=False)

minimum_spanning_tree() 用于计算无向连通图的最小生成树（森林），minimum_spanning_edges() 用于计算无向连通图的最小生成树（森林）的边。对于连通无向图，计算最小生成树；对于非连通无向图，计算最小生成森林。

主要参数：

G(undirected graph)：无向图。

weight(str)：指定用作计算权重的边属性。

algorithm(string)：计算最小生成树的算法，可选项为 ‘kruskal’、‘prim’ 或 ‘boruvka’。默认算法为 ‘kruskal’。

data(bool)：指定返回值是否包括边的权值。

ignore_nan(bool) ：在边的权重为 Nan 时产生异常。

返回值：

minimum_spanning_tree() 的返回值是由最小生成树构成的图，类型为 NetworkX Graph，需要用 T.edges() 获得对应的最小生成树的边。

minimum_spanning_edges() 的返回值是最小生成树的构成边，类型为<class ‘generator’>，需要用 list() 转换为列表数据。

案例：天然气管道铺设问题

问题描述：

某市区有 7个小区需要铺设天然气管道，各小区的位置及可能的管道路线、费用如图所示，要求设计一个管道铺设路线，使天然气能输送到各个小区，且铺设管道的总费用最小。

这是一个最小生成树问题，用 NetworkX 的 minimum_spanning_tree() 函数即可求出费用最小的管道路线。

图的输入。本例为稀疏的有权无向图，使用 G.add_weighted_edges_from() 函数以列表向图中添加多条赋权边，每个赋权边以元组 (node1,node2,weight) 表示。

nx.minimum_spanning_tree() 和 nx.tree.minimum_spanning_edges() 都可以计算最小生成树，参数设置和属性也基本一致，区别主要在于返回值的格式和调用方式。

案例：建设通信网络

在 n 个城市架设 n-1 条线路，建设通信网络。任意两个城市之间都可以建设通信线路，且单位长度的建设成本相同。求建设通信网络的最低成本的线路方案。

（1）城市数 n≥10，由键盘输入；（2）城市坐标 x, y 在（0～100）之间随机生成；（3）输出线路方案的各段线路及长度。

这是一个典型的最小生成树问题。n 个城市构成图的 n 个顶点，任意两个顶点之间都有连接边，边的权值是两个顶点的间距。

输入。

本例程对应案例中的各项约束条件：必须经过图中的绿色节点；必须经过图中的两段绿色路段；必须避开图中的红色路段；尽可能以最少的花费到达终点。

本例程是一个遍历简单路径、判断约束条件的通用框架。

all(n in path for n in (2,4,7,12,13,14)) 的作用，一是判断路径中是否包括必经点 N7、N12；二是判断路径中是否包括必经边 (2,4)、(13,14) 的各顶点，这不仅可以减小计算量，而且能确保下面使用 index() 查找顶点位置时不会发生错误。