✓ 文件回写 ✕ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

概述

最小生成树（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