广度优先搜索 (Breadth First Search)

术语表

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

简介

广度优先搜索算法是一种图遍历算法，给定一个起始节点，它会按照距离由近到远的顺序访问节点，详见 https://en.wikipedia.org/wiki/Breadth-first_search。与之相关的是深度优先搜索算法，深度优先搜索。当搜索目标节点被找到的可能性随着距离增加而降低时，该算法非常有用。该遍历支持多种终止条件，例如达到多个目标节点中的某一个、达到最大深度、耗尽给定的遍历关系开销预算，或者仅遍历整个图。该过程的输出包含有关哪些节点被访问以及访问顺序的信息。

语法

各模式下的广度优先搜索语法

以流 (stream) 模式运行广度优先搜索

CALL gds.bfs.stream(
  graphName: string,
  configuration: map
)
YIELD
  sourceNode: int,
  nodeIds: int,
  path: Path

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

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
sourceNode	整数	`不适用`	否	开始遍历的节点的节点 ID。
targetNodes	整数列表	`空列表`	是	目标节点的 ID。当访问到任何目标节点时，遍历终止。
maxDepth	整数	`-1`	是	从源节点出发，访问节点的最大距离。
1. 在 GDS 会话中，默认值为可用处理器的数量。

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

以流 (stream) 模式运行广度优先搜索

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

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

表 5. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
sourceNode	整数	`不适用`	否	开始遍历的节点的节点 ID。
targetNodes	整数列表	`空列表`	是	目标节点的 ID。当访问到任何目标节点时，遍历终止。
maxDepth	整数	`-1`	是	从源节点出发，访问节点的最大距离。
mutateRelationshipType	字符串	`不适用`	否	用于写入投影图的新关系的关系类型。
2. 在 GDS 会话中，默认值为可用处理器的数量。

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

以统计 (stats) 模式运行广度优先搜索

CALL gds.bfs.stats(
  graphName: string,
  configuration: map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  configuration: Map

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

表 8. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
sourceNode	整数	`不适用`	否	开始遍历的节点的节点 ID。
targetNodes	整数列表	`空列表`	是	目标节点的 ID。当访问到任何目标节点时，遍历终止。
maxDepth	整数	`-1`	是	从源节点出发，访问节点的最大距离。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 9. 结果
名称	类型	描述
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	未使用。
配置	Map	用于运行算法的配置。

示例

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

这些示例将 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.bfs.stream.estimate('myGraph', {
    sourceNode: source
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
RETURN nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 10. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
5	4	536	536	"536 字节"

流模式

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

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

以下命令将运行算法并流式传输结果

MATCH (source:Node{name:'A'})
CALL gds.bfs.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.bfs.stream('myGraph', {
  sourceNode: source,
  targetNodes: targetNodes
})
YIELD path
RETURN path

在下图中，我们可以看到节点的遍历顺序，用关系类型 NEXT 标记。值得注意的是，图中没有 D 节点，这是因为算法首先到达了目标节点 E 并终止了执行，导致 D 未被访问。

运行带有 maxDepth 的广度优先搜索算法

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

在下图中，我们可以看到节点的遍历顺序，用关系类型 NEXT 标记。节点 D 和 E 未被访问，因为它们距离节点 A 的距离为 2。

变更 (Mutate)

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

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

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

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

以下语句将以 mutate 模式运行该算法：

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

表 11. 结果
relationshipsWritten
4

执行上述查询后，内存中的图将被更新为类型为 BFS 的新关系。

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