概述

最小生成树（Minimum Spanning Tree, MST）算法计算图中每个连通分量的边权重之和最小的生成树。

MST在网络设计、聚类和优化等问题中具有各种应用，其中最小化总成本或权重是重要的目标。

基本概念

生成树

一个生成树（Spanning Tree）是一个连通图G = (V, E)（或一个连通分量）的连通子图，它包含图中的所有节点，并形成一个树结构（即无环）。一个图可能存在多个生成树，而每个生成树必定有(|V| - 1)条边。

下图中的11个节点和10条用红色突出显示的边构成该图的一个生成树：

最小生成树（MST）

最小生成树（MST）是边权重和最小的生成树。MST的构建从给定的起点开始。起点的选择不会影响MST算法的正确性，但会影响MST的结构和边的添加顺序。不同的起点可能产生不同的MST，但对于给定的图，它们都是有效的MST。

给上面的示例图赋予边权重后，使用不同起点产生的三个可能的MST在下面以红色突出显示：

关于起点的选择：

• 每个连通分量只需要一个起点。如果指定了多个起点，只有第一个有效。
• 如果某个连通分量没有指定起点，则不会为其计算MST。
• 孤点不是计算MST的有效起点。

特殊说明

• 最小生成树算法忽略边的方向，按照无向边进行计算。

语法

• 命令：algo(mst)
• 参数：

示例

示例图如下，节点A是电力中心，节点B~H是周围的村庄。每条边上标有其UUID和连接位置之间的距离，表示所需的电缆长度：

文件回写

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

直接返回

algo(mst).params({
  ids: 'A',
  edge_schema_property: '@connect.distance'
}) as mst 
return mst

结果：mst

流式返回

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