概述

最小生成树（Minimum Spanning Tree）算法可以计算出一张图的各个连通分量的极小连通子图，并以路径的形式返回这些极小连通子图中的边。最小生成树是图论中的一个基本概念，在路径优化、最低成本的求解中有着重要应用。

一张图的最小生成树可能有多个解，本算法仅计算并返回其中一种解。

基本概念

最小生成树

对于一个含有 n 个节点的连通图来说，其极小连通子图由此 n 个节点以及图中的 n-1 条边构成；这些边使这 n 个节点连通，如果去掉其中任何一条边，则这 n 个节点不再连通；这 n-1 条边构成这张图的一个最小生成树。

下图为一张含有 11 个节点的连通图，图中用绿色标出的 10 条边就是该图的一个最小生成树：

极小连通子图中必然 1）不会出现环路，2）不会出现自环边，3）任意两点之间最多只有一条边。根据这些特征重新分析上面的例子并绘图：

只要 1）去掉红色环路中的任意一条边，2）去掉蓝色自环边，3）保留三条黄色边中的任意一条，就能得到该连通图的最小生成树的一种解。该图的最小生成树共有 4 * 3 = 12 种解。

MST 权重

考虑权重的 MST 是将极小连通子图的中边的权重相加，取权重和最小的解。计算 MST 时考虑权重可能会减少解的个数，但仍然可能有多个解。

如上图所示，已知红色边权重为 2，黑色边权重为 1，则该图的权重 MST 有两个解，每个解中的边用绿色表示，权重和均为 9 * 1 + 1 * 2 = 11：

考虑算法的实际应用，Ultipa 的最小生成树算法必须考虑边的权重。如果不考虑权重，所有的生成树都是最小生成树。

MST 起点

对于连通图，其 MST 中包含的边数 = 图的节点数 - 1；即对于任意一张图，图的节点数 = MST 中包含的边数 + 连通分量个数。

MST 算法需要用户为连通分量指定一个起点才能计算该连通分量的最小生成树，没有指定起点的连通分量则不计算。每个连通分量指定一个起点即可，多指定无效。指定图中的孤点也无效。

如上图所示，指定起点序列 [2, 13, 4, 5, 7]：节点 4 与节点 2 同处一个连通分量，故起点序列中的节点 4 无效；节点 5 是孤点，亦无效。算法按照 [2, 13, 7] 的顺序计算它们各自所在连通分量的 MST；节点 10、11、12 所在的连通分量由于没有指定起点，不参与计算。

特殊处理

孤点、不连通图

孤点不参与最小生成树的计算。

不连通图中，指定了起点的连通分量会在其内部计算最小生成树。

自环边

自环边不参与最小生成树的计算。

有向边

对于有向边，本算法会忽略边的方向，按照无向边进行计算。

结果和统计值

以下面的图为例，1 号点是一个供电中心，2~8 号点是周围的 7 个村落，各条边上标注的公里数代表各位置间的距离（即铺设电缆所需的长度），运行最小生成树算法，找出成本最低的电缆铺设方案：

算法结果：指定 1 号点为起点，用边上的距离属性作为权重，返回 MST（一步路径列表）

8 --[107]-- 1
1 --[108]-- 5
5 --[111]-- 7
7 --[113]-- 6
1 --[101]-- 2
4 --[104]-- 1
3 --[103]-- 4

即成本最低的电缆铺设方案如下：

算法统计值：无

命令和参数配置

• 命令：algo(mst)
• params() 参数配置项如下：

示例：从点 UUID = 1 出发，使用边的属性 distance 作为权重来生成最小生成树，即用真实场景中的“最短距离”连接所有点

algo(mst).params({
  uuids: [1],
  edge_schema_property: distance
}).stream() as a return a

算法执行

任务回写

1. 文件回写

示例：从点 UUID = 1 出发，使用边属性 distance 作为权重生成最小生成树，将算法结果回写至名为 solution 的文件

algo(mst).params({
  uuids: [1],
  edge_schema_property: distance
}).write({
  file:{
    filename: "solution"
    }
})

2. 属性回写

算法不支持属性回写。

3. 统计回写

算法无统计值。

直接返回

示例：从点 UUID = 1 出发，使用边属性 distance 作为权重生成最小生成树，将算法结果定义为别名 mst 并返回

algo(mst).params({
  uuids: [1],
  edge_schema_property: distance
}) as mst 
return mst

流式返回

示例：从点 UUID = 1 出发，使用边属性 distance 作为权重生成最小生成树，返回最小生成树中所有边属性 distance 的和

algo(mst).params({
  uuids: [1],
  edge_schema_property: distance
}).stream() as mst
with pedges(mst) as mstUUID
find().edges(mstUUID) as edges
return sum(edges.distance)

实时统计

算法无统计值。