最小生成树

词汇表

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

简介

最小生成树 (MST) 从给定的节点开始，找到所有可到达的节点，并返回连接这些节点的具有最小可能权重的关系集。Prim 算法是最简单和最著名的最小生成树算法之一。它的操作类似于Dijkstra 最短路径算法，但它不是最小化以每个关系结尾的路径的总长度，而是最小化每个关系的长度。这使得算法能够处理具有负权重的图。

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

最小生成树

用例

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

注意事项

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

语法

本节介绍在每种执行模式下用于执行 Prim 算法的语法。我们正在描述命名的图变体的语法。要了解有关一般语法变体的更多信息，请参见语法概述。

每种模式下的生成树语法

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

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

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

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名的图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名的图。将包含具有任何给定类型的关系。
concurrency	整数	`1`	是	算法是单线程的，更改并发参数不会影响运行时。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更轻松地跟踪算法的进度。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
sourceNode	整数	`空`	n/a	起始源节点 ID。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将无权重运行。
objective	字符串	`'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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定和/或图过滤的配置。

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

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

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

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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定和/或图过滤的配置。

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

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

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

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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定和/或图过滤的配置。

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

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

示例

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

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

在本节中，我们将展示在具体图上运行 Prim 算法的示例。目的是说明结果是什么样子，并提供如何在实际环境中使用该算法的指南。我们将在少数节点以特定模式连接的小型道路网络图上进行此操作。示例图如下所示

以下将创建图中所示的示例图

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	520	520	"520 字节"

流

在 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. 结果
node	parent	weight
"A"	"B"	1.0
"B"	"D"	4.0
"C"	"A"	2.0
"D"	"D"	0.0
"E"	"C"	5.0

统计

在 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 执行模式扩展了 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. 结果
源	目标	成本
"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 执行模式扩展了 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

如您所见，最大加权生成树返回一个不同的树，该树具有更大的关系权重总和。