广度优先搜索 (Breadth First Search)

简介

广度优先搜索 (BFS) 算法从给定节点开始，按距离（跳数）从小到大的顺序访问节点，详情请参阅 https://en.wikipedia.org/wiki/Breadth-first_search。当相关节点随距离增加而减少时，BFS 非常有用。

遍历支持多种终止条件，例如到达多个目标节点中的任意一个、达到最大深度或遍历整个图。

BFS 作业的输出会被写入 Snowflake 表。BFS 路径由单独的链接 source → target 组成，其中 source 和 target 是 BFS 路径上的连续节点。输出表包含这些共同构成 BFS 路径的单个链接。由于 BFS 路径可能穿过带有不同节点标签的节点，因此链接中两个节点的标签都会包含在输出表中。

表 1. 输出表架构
名称 类型 描述

SOURCENODEID

字符串

BFS 路径中链接的“第一个”节点的 ID。数字 ID 会转换为字符串。

TARGETNODEID

字符串

BFS 路径中链接的“第二个”节点的 ID。数字 ID 会转换为字符串。

SOURCELABEL

字符串

链接中“第一个”节点的节点标签名称。

TARGETLABEL

字符串

链接中“第二个”节点的节点标签名称。

我们将此类关系表称为 异构（针对节点标签而言）。

输出表中行的顺序不保证与 BFS 访问顺序一致。此外，由于存在回溯“跳跃”，BFS 探索的链接不一定是原始图中的关系。

语法

本节介绍用于执行广度优先搜索算法的语法。

运行广度优先搜索。
CALL Neo4j_Graph_Analytics.graph.bfs(
  'CPU_X64_XS',                    (1)
  {
    ['defaultTablePrefix': '...',] (2)
    'project': {...},              (3)
    'compute': {...},              (4)
    'write':   {...}               (5)
  }
);
1 计算池选择器。
2 表引用的可选前缀。
3 项目配置。
4 计算配置。
5 写入配置。
表 2. 参数
名称 类型 默认 可选 描述

computePoolSelector

字符串

不适用

否

运行 BFS 作业的计算池选择器。

配置

Map

{}

否

用于图项目、算法计算和结果回写的配置。
有关以下项目配置的更多详细信息，请参阅 项目文档。
表 3. 项目配置
名称 类型

nodeTables

节点表列表。

relationshipTables

关系类型到关系表的映射。
表 4. 计算配置
名称 类型 默认 可选 描述

sourceNode

字符串或整数

不适用

否

开始遍历的节点的节点 ID。

sourceNodeTable

字符串

不适用

否

包含其 NODEID 列中 sourceNode 的全限定节点表。

targetNodes

List<字符串或整数>

[]

是

目标节点标识符集；当到达其中任意一个时停止遍历。

targetNodesTable

字符串

不适用

取决于 targetNodes

包含其 NODEID 列中 targetNodes 的全限定节点表。如果 targetNodes 为空，则可选。

maxDepth

整数

-1

是

访问节点距离源节点的最大距离。值为 -1 表示搜索将持续到任意距离。

resultRelationshipType

字符串

'NEXT'

是

用于回写到 Snowflake 数据库的关系类型。
有关以下写入配置的更多详细信息，请参阅 写入文档。
表 5. 写入配置
名称 类型 默认 可选 描述

outputTable

字符串

不适用

否

关系写入的 Snowflake 数据库表。

关系类型 (relationshipType)

字符串

'NEXT'

是

将回写到 Snowflake 数据库的关系类型。

示例

现在我们来看如何将 BFS 应用于一个小型的有向示例图。该图表示如下

Visualization of the example graph

以下查询用于创建示例图。

-- CREATE DATABASE EXAMPLE_DB; -- to do once
USE DATABASE EXAMPLE_DB;
-- CREATE SCHEMA DATA_SCHEMA; -- to do once
USE SCHEMA DATA_SCHEMA;

CREATE OR REPLACE TABLE nodes_A (nodeId varchar);
INSERT INTO nodes_A (nodeId)
SELECT 'a1' UNION ALL
SELECT 'a2';

CREATE OR REPLACE TABLE nodes_B (nodeId Number);
INSERT INTO nodes_B (nodeId)
SELECT 1 UNION ALL
SELECT 7;

CREATE OR REPLACE TABLE nodes_C (nodeId Number);
INSERT INTO nodes_C (nodeId)
SELECT 1 UNION ALL
SELECT 2;

CREATE OR REPLACE TABLE relationships_R (sourceNodeId varchar, targetNodeId Number);
INSERT INTO relationships_R VALUES ('a1', 7), ('a2', 1);

CREATE OR REPLACE TABLE relationships_S (sourceNodeId varchar, targetNodeId Number);
INSERT INTO relationships_S VALUES ('a1', 1);

CREATE OR REPLACE TABLE relationships_T (sourceNodeId Number, targetNodeId varchar);
INSERT INTO relationships_T VALUES (7, 'a2');

CREATE OR REPLACE TABLE relationships_U (sourceNodeId Number, targetNodeId Number);
INSERT INTO relationships_U VALUES (1, 2);

运行作业（从源进行完整遍历）

运行广度优先搜索作业涉及三个步骤：投影 (Project)、计算 (Compute) 和写入 (Write)。

要运行查询，需要为应用程序、您的消费者角色和您的环境设置必要的权限。请参阅 入门 页面以了解更多信息。

我们还假设应用程序名称为默认的 Neo4j_Graph_Analytics。如果您在安装过程中选择了不同的应用程序名称，请将其替换为该名称。

以下示例从节点 A 运行 BFS，并将 BFS 路径写入输出关系表
CALL Neo4j_Graph_Analytics.graph.bfs('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': ['nodes_A', 'nodes_B', 'nodes_C'],
        'relationshipTables': {
            'relationships_R': {
                'sourceTable': 'nodes_A',
                'targetTable': 'nodes_B'
            },
            'relationships_S': {
                'sourceTable': 'nodes_A',
                'targetTable': 'nodes_C'
            },
            'relationships_T': {
                'sourceTable': 'nodes_B',
                'targetTable': 'nodes_A'
            },
            'relationships_U': {
                'sourceTable': 'nodes_B',
                'targetTable': 'nodes_C'
            }
        }
    },
    'compute': {
      'sourceNodeTable': 'nodes_A',
      'sourceNode': 'a1',
      'targetNodesTable': 'nodes_C',
      'targetNodes': [2], -- will not be reached due to maxDepth
      'maxDepth': 2
    },
    'write': [{'outputTable': 'BFS_NEXT'}]
})
表 6. 结果
JOB_ID JOB_STATUS JOB_START JOB_END JOB_RESULT

job_8a3f2e0b1c4248d3a0f3a9f0e3f1abcd

SUCCESS

2025-06-30 11:05:12.210

2025-06-30 11:05:16.845

 
 {
    "bfs_1": {
      "computeMillis": 12,
      "configuration": {
        "concurrency": 6,
        "maxDepth": 2,
        "resultRelationshipType": "NEXT",
        "nodeLabels": [
          "*"
        ],
        "relationshipTypes": [
          "*"
        ],
        "sourceNode": "a1",
        "sourceNodeTable": "EXAMPLE_DB.DATA_SCHEMA.nodes_A",
        "targetNodes": [
          2
        ],
        "targetNodesTable": "EXAMPLE_DB.DATA_SCHEMA.nodes_C"
      }
    },
    "project_1": {
      "graphName": "snowgraph",
      "nodeCount": 6,
      "nodeLabels": ...,
      "nodeMillis": 308,
      "relationshipCount": 5,
      "relationshipMillis": 572,
      "relationshipTypes": ...,
      "totalMillis": 880
    },
    "write_relationship_type_1": {
      "outputTable": "EXAMPLE_DB.DATA_SCHEMA.BFS_NEXT",
      "relationshipProperty": "<none>",
      "relationshipType": "NEXT",
      "rowsWritten": 3,
      "writeMillis": 2162
    }
  }

现在我们可以按照以下方式查询写入的结果。

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.BFS_NEXT;
表 7. 可能的结果
SOURCENODEID TARGETNODEID SOURCELABEL TARGETLABEL

a1

1

nodes_A

nodes_C

7

a2

nodes_B

nodes_A

1

7

nodes_C

nodes_B

这些行共同代表了 BFS 的访问顺序 ('a1': nodes_A) → (1: nodes_C) → (7: nodes_B) → ('a2': nodes_A)。该路径包含了所有深度为 2 或以下的节点，因为唯一的目标节点 (2: nodes_C) 深度更深，只会稍后被访问。节点 (1: nodes_B) 的深度为 3，虽然小于目标节点的深度，但超过了配置的最大深度 2；因此它也不会被探索。