深度优先搜索

词汇表

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

简介

深度优先搜索算法是一种图遍历算法，它从给定的节点开始，沿着每条分支尽可能地深入探索，然后再回溯，参见https://en.wikipedia.org/wiki/Depth-first_search。一个相关的算法是广度优先搜索算法，广度优先搜索。例如，如果想要查找距离较远的目标节点，并且探索随机路径有相当大的成功概率，则可以选择此算法而不是广度优先搜索算法。遍历支持多种终止条件，基于到达多个目标节点之一、达到最大深度、耗尽给定遍历关系成本的预算或仅仅遍历整个图。过程的输出包含有关哪些节点被访问以及访问顺序的信息。

语法

每个模式下的深度优先搜索语法

以流模式运行深度优先搜索

CALL gds.dfs.stream(
  graphName: String,
  configuration: Map
)
YIELD
  sourceNode: Integer,
  nodeIds: Integer,
  path: Path

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

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`1`	是	该算法是单线程的，更改并发参数不会影响运行时间。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更容易跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
sourceNode	整数	`n/a`	否	要从其开始遍历的节点的节点 ID。
targetNodes	整数列表	`空列表`	是	目标节点的 ID。当访问任何目标节点时，遍历终止。
maxDepth	整数	`-1`	是	访问节点与源节点的最大距离。

表 3. 结果
名称	类型	描述
sourceNode	整数	要从其开始遍历的节点的节点 ID。
nodeIds	整数列表	在遍历期间访问的所有节点的 ID。
path	路径	包含在遍历期间访问的所有节点的路径。

以流模式运行深度优先搜索

CALL gds.dfs.mutate(
  graphName: string,
  configuration: map
)
YIELD
  relationshipsWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  mutateMillis: Integer,
  configuration: Map

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

表 5. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`1`	是	该算法是单线程的，更改并发参数不会影响运行时间。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更容易跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
sourceNode	整数	`n/a`	否	要从其开始遍历的节点的节点 ID。
targetNodes	整数列表	`空列表`	是	目标节点的 ID。当访问任何目标节点时，遍历终止。
maxDepth	整数	`-1`	是	访问节点与源节点的最大距离。
mutateRelationshipType	字符串	`n/a`	否	写入投影图的新关系使用的关系类型。

表 6. 结果
名称	类型	描述
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	未使用。
mutateMillis	整数	向投影图添加关系的毫秒数。
relationshipsWritten	整数	添加的关系数。
configuration	映射	用于运行算法的配置。

示例

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

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

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

考虑由以下 Cypher 语句投影的图

CREATE
       (nA:Node {name: 'A'}),
       (nB:Node {name: 'B'}),
       (nC:Node {name: 'C'}),
       (nD:Node {name: 'D'}),
       (nE:Node {name: 'E'}),

       (nA)-[:REL]->(nB),
       (nA)-[:REL]->(nC),
       (nB)-[:REL]->(nE),
       (nC)-[:REL]->(nD)

以下语句将投影图并将其存储在图目录中。

MATCH (source:Node)-[r:REL]->(target:Node)
RETURN gds.graph.project(
  'myGraph',
  source,
  target
)

在以下示例中，我们将演示在此图上使用深度优先搜索算法。

内存估算

首先，我们将使用estimate过程估算运行算法的成本。这可以使用任何执行模式完成。在本例中，我们将使用stream模式。估算算法有助于了解在您的图上运行算法将产生的内存影响。当您稍后在其中一个执行模式下实际运行算法时，系统将执行估算。如果估算表明执行超出其内存限制的可能性非常高，则会禁止执行。有关此内容的更多信息，请参见自动估算和执行阻止。

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

以下将估算以流模式运行算法的内存需求

MATCH (source:Node {name: 'A'})
CALL gds.dfs.stream.estimate('myGraph', {
  sourceNode: source
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
RETURN nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 7. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
5	4	352	352	"352 字节"

流

在stream执行模式下，算法按遍历顺序返回每个关系的路径。这使我们能够直接检查结果或在 Cypher 中对其进行后处理，而不会产生任何副作用。

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

运行深度优先搜索算法

MATCH (source:Node{name:'A'})
CALL gds.dfs.stream('myGraph', {
  sourceNode: source
})
YIELD path
RETURN path

如果我们没有指定任何提前终止选项，算法将遍历整个图：在下图中，我们可以看到节点的遍历顺序，由关系类型NEXT标记

使用目标节点运行深度优先搜索算法

MATCH (source:Node{name:'A'}), (d:Node{name:'D'}), (e:Node{name:'E'})
WITH source, [d, e] AS targetNodes
CALL gds.dfs.stream('myGraph', {
  sourceNode: source,
  targetNodes: targetNodes
})
YIELD path
RETURN path

如果指定节点D和E作为目标节点，则由于深度优先遍历顺序，并非所有距离为 1 的节点都将被访问，其中节点D在B之前到达。

使用maxDepth运行深度优先搜索算法

MATCH (source:Node{name:'A'})
CALL gds.dfs.stream('myGraph', {
  sourceNode: source,
  maxDepth: 1
})
YIELD path
RETURN path

在上述情况下，节点D和E未被访问，因为它们与节点A的距离为 2。

变异

mutate执行模式使用新关系更新命名图。深度优先搜索算法返回的路径是线图，其中节点按算法访问它们的顺序出现。关系类型必须使用mutateRelationshipType选项进行配置。

当多个算法结合使用时，mutate模式特别有用。

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

深度优先搜索mutate支持与stream模式相同的提前终止条件。

以下将在mutate模式下运行算法

MATCH (source:Node{name:'A'})
CALL gds.dfs.mutate('myGraph', {
  sourceNode: source,
  mutateRelationshipType: 'DFS'
})
YIELD relationshipsWritten
RETURN relationshipsWritten

表 8. 结果
relationshipsWritten
4

执行上述查询后，内存中的图将使用类型为DFS的新关系进行更新。

即使输入图是无向图，生成的关系也始终是有向的。