概述
最小生成树(Minimum Spanning Tree, MST)算法计算图中每个连通分量的边权重之和最小的生成树。
MST在网络设计、聚类和优化等问题中具有各种应用,其中最小化总成本或权重是重要的目标。
基本概念
生成树
一个生成树(Spanning Tree)是一个连通图G = (V, E)(或一个连通分量)的连通子图,它包含图中的所有节点,并形成一个树结构(即无环)。一个图可能存在多个生成树,而每个生成树必定有(|V| - 1)条边。
下图中的11个节点和10条用红色突出显示的边构成该图的一个生成树:
![](https://img.ultipa.cn/draw/draw_0c34b3642e464fc8a2a536844032f142.jpg?v='1689661402106')
最小生成树(MST)
最小生成树(MST)是边权重和最小的生成树。MST的构建从给定的起点开始。起点的选择不会影响MST算法的正确性,但会影响MST的结构和边的添加顺序。不同的起点可能产生不同的MST,但对于给定的图,它们都是有效的MST。
给上面的示例图赋予边权重后,使用不同起点产生的三个可能的MST在下面以红色突出显示:
![](https://img.ultipa.cn/draw/draw_f328b3c4a99c4bf8a075d69897400c50.jpg?v='1689661304468')
关于起点的选择:
- 每个连通分量只需要一个起点。如果指定了多个起点,只有第一个有效。
- 如果某个连通分量没有指定起点,则不会为其计算MST。
- 孤点不是计算MST的有效起点。
![](https://img.ultipa.cn/draw/draw_720492664e30472299567955274233dd.jpg?v='1689661829537')
特殊说明
- 最小生成树算法忽略边的方向,按照无向边进行计算。
语法
- 命令:
algo(mst)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
ids / uuids | []_id / []_uuid |
/ | / | 是 | 起点的ID/UUID;如果忽略,系统将为每个连通分量选择一个起点 |
edge_schema_property | []@<schema>?.<property> |
数值类型,需LTE | / | 否 | 用作边权重的属性,权重值为所有指定属性值中的最小值;没有任何指定属性的边不参与构成MST |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
示例
示例图如下,节点A是电力中心,节点B~H是周围的村庄。每条边上标有其UUID和连接位置之间的距离,表示所需的电缆长度:
![](https://img.ultipa.cn/draw/draw_6300a3807703469db1464b17f1507fca.jpg?v='1689665496141')
文件回写
配置项 |
回写内容 |
描述 |
---|---|---|
filename | _id--[_uuid]--_id |
MST中的一步路径:(起点)--(边)--(终点) |
algo(mst).params({
uuids: [1],
edge_schema_property: 'distance'
}).write({
file:{
filename: 'solution'
}
})
结果:文件solution
A--[107]--H
A--[108]--E
E--[111]--G
F--[113]--G
A--[101]--B
A--[104]--D
C--[103]--D
直接返回
别名序号 |
类型 |
描述 |
---|---|---|
0 | []path | MST中的一步路径:_uuid (起点) -- [_uuid ] (边) -- _uuid (终点) |
algo(mst).params({
ids: 'A',
edge_schema_property: '@connect.distance'
}) as mst
return mst
结果:mst
1--[107]--8 |
1--[108]--5 |
5--[111]--7 |
6--[113]--7 |
1--[101]--2 |
1--[104]--4 |
3--[103]--4 |
流式返回
别名序号 |
类型 |
描述 |
---|---|---|
0 | []path | MST中的一步路径:_uuid (起点) -- [_uuid ] (边) -- _uuid (终点) |
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)
结果:5.65