Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/minimum_spanning_tree/
Documentation version: v5.3.2

# 最小生成树

本文介绍最小生成树算法，并演示如何用 GQL 实现该算法。

## 算法介绍

最小生成树用于在保持全图连通的前提下，使边权总和最小。

该过程将算法逻辑封装为可复用过程，可直接在图数据上执行并输出结果。

更多信息，请参见[最小生成树](https://zh.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91)。

## 数据模型

为了在 GQL 中实现最小生成树算法，使用以下数据模型创建图类型：

- 实体由类型为`Node`的点表示，点属性包括`id`和`rating`。
- 实体间关系由类型为`Link`的边表示，边属性包括`weight`。

该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/minimum_spanning_tree/#1_prepare_graph_data)。

## 过程实现[]()

为了计算最小生成树结果，创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)。

关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/minimum_spanning_tree/#procedure_implement)。下文将介绍该过程的关键组成部分及其工作原理。

该过程接受以下输入参数：

- `start_id`：`INT64`类型。 最小生成树起始生长的点 ID。

此外，在过程内部定义了以下变量：

 | 变量名 | 变量类型 | 描述
 | `frontier` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 已加入 MST 的活跃点集合。
 | `has_next` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 是否仍有跨越边可加入 MST。
 | `step_no` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前 MST 边的步骤计数。
 | `total_weight` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 已选 MST 边的累积总权重。
 | `pick_src` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 所选最小跨越边的源点。
 | `pick_dst` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 所选最小跨越边的目标点。
 | `pick_weight` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 所选最小跨越边的权重。
 | `best_edge` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 当前步骤中全局最小权重跨越边。
 | `in_tree` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点标志：该点已是 MST 的一部分。
 | `cand` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 到达该点的最轻跨越边候选。
 | `result_table` | [表变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/table-variable/) | 存储 MST 边（step_no, src_id, dst_id, weight）的输出表。

以下步骤概述了该过程的逻辑：

1. 从任意点启动 MST，将其加入`frontier`（树内集合）。
2. 使用`best_edge`找出从树内点到树外点权重最小的跨越边。
3. 将所选边及其目标点加入 MST，更新`total_weight`和`step_no`。
4. 重复执行直至所有点都在树内或没有跨越边。返回 MST 边列表。

## 操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。

### 1. 准备图数据[]()

1. 

创建一个与数据模型匹配的图类型。

````
'''
CREATE GRAPH TYPE IF NOT EXISTS minimum_spanning_tree_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

````

2. 

下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/minimum_spanning_tree/`：

  - [minimum_spanning_tree_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/minimum_spanning_tree/minimum_spanning_tree_node.csv)：点数据。
  - [minimum_spanning_tree_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/minimum_spanning_tree/minimum_spanning_tree_edge.csv)：边数据。

查看 CSV 内容

minimum_spanning_tree_node.csv

````
id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

````

minimum_spanning_tree_edge.csv

````
src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

````

3. 

基于图类型创建临时图，并将数据文件加载到临时图中。

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #minimum_spanning_tree_graph TYPED minimum_spanning_tree_graph_type

````

````
'''
USE #minimum_spanning_tree_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/minimum_spanning_tree/minimum_spanning_tree_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/minimum_spanning_tree/minimum_spanning_tree_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

````

导入成功后，在控制台执行以下查询核对点数：

````
'''
USE #minimum_spanning_tree_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

`node_count`应为`24`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。

### 2. 创建过程[]()

创建实现最小生成树算法的过程。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/minimum_spanning_tree/#procedure_implement)。 

````
'''
CREATE OR REPLACE PROCEDURE minimum_spanning_tree(start_id INT64)
RETURNS (step_no INT64, src_id INT64, dst_id INT64, weight DOUBLE, total_weight DOUBLE)
COMMENT "Compute a minimum spanning tree for the connected component that contains start_id in an undirected weighted graph whose vertex primary key is id and edge weight property is weight."
AS {
  VALUE frontier ACTIVE_SET

  VALUE has_next BOOLEAN = true
  VALUE step_no INT64 = 0
  VALUE total_weight DOUBLE = 0.0
  VALUE pick_src INT64 = 0
  VALUE pick_dst INT64 = 0
  VALUE pick_weight DOUBLE = 0.0

  VALUE best_edge TopKAgg<1, weight DOUBLE ASC, src_id INT64 ASC, dst_id INT64 ASC>

  NODE VALUE in_tree OrAgg = false
  NODE VALUE cand TopKAgg<1, weight DOUBLE ASC, src_id INT64 ASC, dst_id INT64 ASC>

  TABLE result_table TYPED TABLE {step_no INT64, src_id INT64, dst_id INT64, weight DOUBLE}

  MATCH (s)
  WHERE s.id = start_id
  PER NODE (s) {
    SET s.@in_tree = true
  }

  WHILE has_next = true THEN {
    MATCH (s)
    WHERE s.@in_tree = true
    PER NODE (s) {
      SET s.@in_tree = true
    }
    FINALLY {
      SET frontier = s
    }

    MATCH (t)
    WHERE t.@in_tree = false
    PER NODE (t) {
      SET t.@cand.clear()
    }

    SET @best_edge.clear()

    MATCH (s)-[e]-(t)
    WHERE s IN frontier AND t.@in_tree = false
    PER PATH {
      SET t.@cand += RECORD{weight: e.weight, src_id: s.id, dst_id: t.id}
    }

    MATCH (t)
    WHERE t.@in_tree = false AND t.@cand.size() > 0
    PER NODE (t) {
      SET @best_edge += t.@cand.min()
    }

    IF @best_edge.size() = 0 THEN {
      SET has_next = false
    }
    ELSE {
      SET pick_weight = @best_edge.min().weight
      SET pick_src = @best_edge.min().src_id
      SET pick_dst = @best_edge.min().dst_id
      SET step_no = step_no + 1
      SET total_weight = total_weight + pick_weight

      EXPORT step_no, pick_src, pick_dst, pick_weight INTO result_table

      MATCH (t)
      WHERE t.id = pick_dst
      PER NODE (t) {
        SET t.@in_tree = true
      }
    }
  }

  FOR r IN result_table
  RETURN
    r.step_no AS step_no,
    r.src_id AS src_id,
    r.dst_id AS dst_id,
    r.weight AS weight,
    total_weight AS total_weight
  ORDER BY step_no ASC
}
'''

````

### 3. 调用过程[]()

从点`1`开始构建最小生成树，返回选中的边及总权重。

````
USE #minimum_spanning_tree_graph CALL minimum_spanning_tree(1) RETURN step_no, src_id, dst_id, weight, total_weight

````

返回：

展开查看返回

````
+---------+--------+--------+--------+--------------+
| step_no | src_id | dst_id | weight | total_weight |
+---------+--------+--------+--------+--------------+
| 12      | 19     | 21     | 1.0    | 49.0         |
| 23      | 23     | 24     | 1.0    | 49.0         |
| 22      | 21     | 23     | 4.0    | 49.0         |
| 21      | 3      | 5      | 4.0    | 49.0         |
| 20      | 21     | 20     | 3.0    | 49.0         |
| 19      | 12     | 11     | 2.0    | 49.0         |
| 18      | 12     | 10     | 1.0    | 49.0         |
| 17      | 14     | 12     | 3.0    | 49.0         |
| 16      | 18     | 17     | 2.0    | 49.0         |
| 15      | 18     | 14     | 2.0    | 49.0         |
| 14      | 16     | 18     | 3.0    | 49.0         |
| 13      | 21     | 22     | 2.0    | 49.0         |
| 1       | 1      | 3      | 2.0    | 49.0         |
| 11      | 15     | 19     | 3.0    | 49.0         |
| 10      | 15     | 16     | 1.0    | 49.0         |
| 9       | 13     | 15     | 2.0    | 49.0         |
| 8       | 9      | 13     | 2.0    | 49.0         |
| 7       | 9      | 7      | 2.0    | 49.0         |
| 6       | 8      | 9      | 3.0    | 49.0         |
| 5       | 6      | 4      | 2.0    | 49.0         |
| 4       | 6      | 8      | 1.0    | 49.0         |
| 3       | 2      | 6      | 2.0    | 49.0         |
| 2       | 3      | 2      | 1.0    | 49.0         |
+---------+--------+--------+--------+--------------+

````

保存结果到文件或图中

如需将返回的结果保存为 CSV 文件或写入图，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)。导出字段应与返回列及目标属性对应。