概述

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

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

基本概念

生成树

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

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

最小生成树（MST）

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

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

关于起点的选择：

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

特殊说明

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

示例图集

创建示例图集：

// 在空图集中逐行运行以下语句
create().node_schema("electricCenter").node_schema("village").edge_schema("connects")
create().edge_property(@connects, "distance", float)
insert().into(@electricCenter).nodes([{_id:"A"}])
insert().into(@village).nodes([{_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}, {_id:"H"}])
insert().into(@connects).edges([{_from:"A", _to:"B", distance: 1}, {_from:"B", _to:"C", distance: 1.3},{_from:"C", _to:"D", distance: 1}, {_from:"A", _to:"D", distance: 1.2}, {_from:"A", _to:"C", distance: 2.4}, {_from:"D", _to:"H", distance: 1.65}, {_from:"A", _to:"H", distance: 0.4}, {_from:"A", _to:"E", distance: 0.7}, {_from:"A", _to:"F", distance: 2.2}, {_from:"A", _to:"G", distance: 1.6}, {_from:"E", _to:"G", distance: 0.9}, {_from:"E", _to:"F", distance: 1.27}, {_from:"F", _to:"G", distance: 0.45}])

创建HDC图集

将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_mst：

CALL hdc.graph.create("hdc-server-1", "hdc_mst", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_mst", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

参数

算法名：algo(mst)

文件回写

CALL algo.mst.write("hdc_mst", {
  params: {
    return_id_uuid: "id",
    ids: ["A"],
    edge_schema_property: "distance"
  },
  return_params: {
    file: {
      filename: "paths"
    }
  }
})

algo(mst).params({
  project: "hdc_mst",
  return_id_uuid: "id",
  ids: ["A"],
  edge_schema_property: "distance"
}).write({
  file: {
    filename: "paths"
  }
})

结果：

A--[107]--H
A--[108]--E
E--[111]--G
F--[113]--G
A--[101]--B
A--[104]--D
C--[103]--D

完整返回

CALL algo.mst("hdc_mst", {
  params: {
    ids: ["A"],
    edge_schema_property: "@connects.distance"
  },
  return_params: {}
}) YIELD mst
RETURN mst

exec{
  algo(mst).params({
    ids: ["A"],
    edge_schema_property: "@connects.distance"
  }) as mst
  return mst
} on hdc_mst

结果：

流式返回

CALL algo.mst("hdc_mst", {
  params: {
    ids: ["A"],
    edge_schema_property: "distance"
  },
  return_params: {}
}) YIELD mst
FOR e1 IN pedges(mst)
MATCH ()-[e2 WHERE e2._uuid = e1._uuid]->()
RETURN sum(e2.distance)

exec{
  algo(mst).params({
    ids: ["A"],
    edge_schema_property: "distance"
  }).stream() as mst
  uncollect pedges(mst) as e1
  find().edges({_uuid == e1._uuid}) as e2
  return sum(e2.distance)
} on hdc_mst

结果：5.65