最小权重生成树 (Minimum Weight Spanning Tree)

术语表

有向: 有向特征。该算法在有向图上定义良好。
有向: 有向特征。该算法忽略图的方向。
有向: 有向特征。该算法不能在有向图上运行。
无向: 无向特征。该算法在无向图上定义良好。
无向: 无向特征。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法有能力区分不同类型的节点。
异构节点: 异构节点允许。该算法平等对待所有选定的节点，无论其标签如何。
异构关系: 异构关系完全支持。该算法有能力区分不同类型的关系。
异构关系: 异构关系允许。该算法平等对待所有选定的关系，无论其类型如何。
加权关系: 加权特征。该算法支持将关系属性用作权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特征。该算法将每个关系视为同等重要，忽略任何关系权重值。
节点属性: 节点属性特征。该算法使用节点属性。

简介

最小权重生成树 (MST) 从给定的节点开始，查找其所有可达节点，并返回连接这些节点且总权重最小的关系集合。普里姆算法 (Prim’s algorithm) 是最简单且最著名的最小生成树算法之一。它的操作类似于 Dijkstra 最短路径算法，但它不是最小化到达每个关系路径的总长度，而是单独最小化每个关系的长度。这使得该算法适用于具有负权重的图。

有关此算法的更多信息，请参阅

最小生成树

使用场景

最小生成树已被用于分析巴布亚新几内亚的航空和海运连接，并最大限度地降低探索该国的旅行成本。例如，它们被用于帮助设计访问全国多个目的地的低成本旅游线路。请参阅 “最小生成树在旅行规划中的应用”。
最小生成树已被用于基于货币收益率之间的相关性，分析和可视化货币网络中的相关性。这在 “最小生成树在货币市场中的应用” 中有描述。
最小生成树也被证明是追踪疫情中感染传播的有用工具。请参阅 “利用最小生成树模型进行丙型肝炎病毒感染医院内暴发的分子流行病学调查”。

注意事项

MST 算法仅在关系具有不同权重的图上运行时才能提供有意义的结果。如果图没有权重（或所有关系具有相同的权重），则任何生成树也是最小生成树。该算法的实现使用单线程执行。更改并发配置无效。

语法

本节介绍在每种执行模式下执行普里姆算法所使用的语法。我们描述的是命名图变体的语法。要了解有关通用语法变体的更多信息，请参阅语法概述。

各模式下的生成树语法

在命名图上以流模式运行算法。

CALL gds.spanningTree.stream(
  graphName: String,
  configuration: Map
)
YIELD
      nodeId: Integer,
      parentId: Integer,
      weight: Float

表 1. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`1`	是	该算法为单线程，更改并发参数对运行时没有影响。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
sourceNode	整数	`不适用`	否	起始源节点 ID。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
目标	字符串	`‘minimum’`	是	如果指定，该参数决定是查找最小还是最大权重生成树。默认情况下，返回最小权重生成树。允许的值为 'minimum' 和 'maximum'。

表 3. 结果
名称	类型	描述
nodeId	整数	发现的生成树中的一个节点
parentId	整数	nodeId 在生成树中的父节点；如果 nodeId 是源节点，则为其自身。
weight	浮点数	从 parentId 到 nodeId 的关系权重。

在命名图上以统计模式运行算法。

CALL gds.spanningTree.stats(
  graphName: String,
  configuration: Map
)
YIELD
      effectiveNodeCount: Integer,
      totalWeight: Float,
      preProcessingMillis: Integer,
      computeMillis: Integer,
      configuration: Map

表 4. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 5. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`1`	是	该算法为单线程，更改并发参数对运行时没有影响。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
sourceNode	整数	`不适用`	否	起始源节点 ID。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
目标	字符串	`‘minimum’`	是	如果指定，该参数决定是查找最小还是最大权重生成树。默认情况下，返回最小权重生成树。允许的值为 'minimum' 和 'maximum'。

表 6. 结果
名称	类型	描述
effectiveNodeCount	整数	已访问节点的数量。
totalWeight	浮点数	生成树中关系权重的总和。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
配置	Map	用于运行算法的配置。

在命名图上以写入模式运行生成树算法。

CALL gds.spanningTree.write(
  graphName: String,
  configuration: Map
)
YIELD
      effectiveNodeCount: Integer,
      totalWeight: Float,
      relationshipsWritten: Integer,
      preProcessingMillis: Integer,
      computeMillis: Integer,
      writeMillis: Integer,
      configuration: Map

表 7. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 8. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`1`	是	该算法为单线程，更改并发参数对运行时没有影响。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeRelationshipType	字符串	`不适用`	否	用于将计算出的关系持久化到 Neo4j 数据库的关系类型。
writeProperty	字符串	`不适用`	否	写入权重的 Neo4j 数据库中的关系属性。
sourceNode	整数	`不适用`	否	起始源节点 ID。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
目标	字符串	`‘minimum’`	是	如果指定，该参数决定是查找最小还是最大权重生成树。默认情况下，返回最小权重生成树。允许的值为 'minimum' 和 'maximum'。

表 9. 结果
名称	类型	描述
effectiveNodeCount	整数	已访问节点的数量。
totalWeight	浮点数	生成树中关系权重的总和。
relationshipsWritten	整数	写入图中的关系数量。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
writeMillis	整数	将结果数据写回的毫秒数。
配置	Map	用于运行算法的配置。

在命名图上以写入模式运行生成树算法。

CALL gds.spanningTree.mutate(
  graphName: String,
  configuration: Map
)
YIELD
      effectiveNodeCount: Integer,
      totalWeight: Float,
      relationshipsWritten: Integer,
      preProcessingMillis: Integer,
      computeMillis: Integer,
      mutateMillis: Integer,
      configuration: Map

表 10. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 11. 配置
名称	类型	默认	可选	描述
mutateRelationshipType	字符串	`不适用`	否	用于写入投影图的新关系的关系类型。
mutateProperty	字符串	`不适用`	否	写入权重的 GDS 图中的关系属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
sourceNode	整数	`不适用`	否	起始源节点 ID。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
目标	字符串	`‘minimum’`	是	如果指定，该参数决定是查找最小还是最大权重生成树。默认情况下，返回最小权重生成树。允许的值为 'minimum' 和 'maximum'。

表 12. 结果
名称	类型	描述
effectiveNodeCount	整数	已访问节点的数量。
totalWeight	浮点数	生成树中关系权重的总和。
relationshipsWritten	整数	添加到内存图中关系的数量。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
mutateMillis	整数	将结果数据写回的毫秒数。
配置	Map	用于运行算法的配置。

示例

以下所有示例应在空数据库中运行。

这些示例将 Cypher 投影作为规范。原生投影将在未来版本中弃用。

在本节中，我们将展示在具体图上运行普里姆算法的示例。目的是说明结果的样子，并为如何在实际环境中使用该算法提供指导。我们将在一个由少数几个按特定模式连接的节点组成的小型道路网络图上进行演示。示例图如下所示

以下代码将创建图中描绘的示例图

CREATE (a:Place {id: 'A'}),
       (b:Place {id: 'B'}),
       (c:Place {id: 'C'}),
       (d:Place {id: 'D'}),
       (e:Place {id: 'E'}),
       (f:Place {id: 'F'}),
       (g:Place {id: 'G'}),
       (d)-[:LINK {cost:4}]->(b),
       (d)-[:LINK {cost:6}]->(e),
       (b)-[:LINK {cost:1}]->(a),
       (b)-[:LINK {cost:3}]->(c),
       (a)-[:LINK {cost:2}]->(c),
       (c)-[:LINK {cost:5}]->(e),
       (f)-[:LINK {cost:1}]->(g);

以下代码将投影并存储一个命名图

MATCH (source:Place)-[r:LINK]->(target:Place)
RETURN gds.graph.project(
  'graph',
  source,
  target,
  { relationshipProperties: r { .cost } },
  { undirectedRelationshipTypes: ['*'] }
)

内存估算

首先，我们将使用 estimate 过程估算运行该算法的成本。这可以在任何执行模式下完成。在此示例中，我们将使用 stats 模式。估算算法对于理解在图上运行算法对内存的影响非常有用。当您随后在某种执行模式下实际运行算法时，系统将执行一次估算。如果估算结果显示执行超出其内存限制的概率极高，则会禁止执行。要阅读更多关于此的内容，请参见自动估算和执行阻塞。

有关 estimate 的更多详细信息，请参阅内存估算。

以下代码将估算以统计模式运行算法所需的内存

MATCH (n:Place {id: 'D'})
CALL gds.spanningTree.stats.estimate('graph', {sourceNode: id(n),relationshipWeightProperty:'cost'})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
RETURN nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
7	14	512	512	“512 字节”

流式输出 (Stream)

在 stream 执行模式下，算法返回每个关系的权重。这允许我们直接检查结果或在 Cypher 中进行后处理，而不会产生任何副作用。

有关 stream 模式的更多详细信息，请参阅流式读取。

以下代码将以流模式运行最小权重生成树算法，并返回每个有效节点的结果。

MATCH (n:Place{id: 'D'})
CALL gds.spanningTree.stream('graph', {
  sourceNode: n,
  relationshipWeightProperty: 'cost'
})
YIELD nodeId,parentId, weight
RETURN gds.util.asNode(nodeId).id AS node, gds.util.asNode(parentId).id AS parent,weight
ORDER BY node

表 14. 结果
节点	parent	weight
"A"	"B"	1.0
"B"	"D"	4.0
"C"	"A"	2.0
"D"	"D"	0.0
"E"	"C"	5.0

统计信息 (Stats)

在 stats 执行模式下，算法返回一行包含算法结果摘要的数据。此执行模式没有任何副作用。它可用于通过检查 computeMillis 返回项来评估算法性能。在下面的示例中，我们将省略返回的时间信息。该过程的完整签名可以在语法章节中找到。

有关 stats 模式的更多详细信息，请参阅统计。

以下代码将运行最小权重生成树算法并返回其统计信息。

MATCH (n:Place{id: 'D'})
CALL gds.spanningTree.stats('graph', {
  sourceNode: n,
  relationshipWeightProperty: 'cost'
})
YIELD effectiveNodeCount, totalWeight
RETURN effectiveNodeCount, totalWeight

表 15. 结果
effectiveNodeCount	totalWeight
5	12.0

写入 (Write)

write 执行模式扩展了 stats 模式，具有一个重要的副作用：将每个关系的权重作为属性写入 Neo4j 数据库。新属性的名称通过强制配置参数 writeProperty 指定。结果是单行摘要，类似于 stats，但包含一些额外的指标。write 模式允许直接将结果持久化到数据库中。

有关 write 模式的更多详细信息，请参阅写入。

以下代码将运行最小权重生成树算法并将结果写回图中。

MATCH (n:Place {id: 'D'})
CALL gds.spanningTree.write('graph', {
  sourceNode: n,
  relationshipWeightProperty: 'cost',
  writeProperty: 'writeCost',
  writeRelationshipType: 'MINST'
})
YIELD preProcessingMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN preProcessingMillis, computeMillis, writeMillis, effectiveNodeCount;

要查找最小生成树中包含的关系，我们可以运行以下查询

MATCH path = (n:Place {id: 'D'})-[:MINST*]-()
WITH relationships(path) AS rels
UNWIND rels AS rel
WITH DISTINCT rel AS rel
RETURN startNode(rel).id AS Source, endNode(rel).id AS Destination, rel.writeCost AS Cost

表 16. 结果
源 (Source)	目的地	成本
"D"	"B"	4.0
"B"	"A"	1.0
"A"	"C"	2.0
"C"	"E"	5.0

最小生成树排除了从 D 到 E 的成本为 6 的关系，以及从 B 到 C 的成本为 3 的关系。节点 F 和 G 未被包括在内，因为它们无法从 D 到达。

写回图中的关系始终是有向的，即使输入图是无向的。

变异 (Mutate)

mutate 执行模式扩展了 stats 模式，具有一个重要的副作用：使用包含该关系权重的新关系属性更新命名图。新属性的名称通过强制配置参数 mutateProperty 指定。结果是单行摘要，类似于 stats，但包含一些额外的指标。当多个算法结合使用时，mutate 模式特别有用。

有关 mutate 模式的更多详细信息，请参阅变更。

以下代码将运行最小权重生成树算法并修改内存中的图。

MATCH (n:Place {id: 'D'})
CALL gds.spanningTree.mutate('graph', {
  sourceNode: n,
  relationshipWeightProperty: 'cost',
  mutateProperty: 'writeCost',
  mutateRelationshipType: 'MINST'
})
YIELD relationshipsWritten
RETURN relationshipsWritten

表 17. 结果
relationshipsWritten
4

添加回图中的关系始终是有向的，即使输入图是无向的。

最大生成树

最大加权生成树算法与最小生成树算法类似，不同之处在于它返回的是组件中所有节点构成的生成树，且关系的总权重最大化。

以下代码将运行最大权重生成树算法并返回其统计信息。

MATCH (n:Place{id: 'D'})
CALL gds.spanningTree.stats('graph', {
  sourceNode: n,
  relationshipWeightProperty: 'cost',
  objective: 'maximum'
})
YIELD totalWeight
RETURN totalWeight

表 18. 结果
totalWeight
17.0

可以看出，最大加权生成树返回了不同的树，其关系权重之和更大。