Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/bfs/
Documentation version: v5.3.2

# 广度优先搜索（BFS）

本文介绍广度优先搜索（Breadth-First Search, BFS）算法，并演示如何用 GQL 实现。

## 算法简介

BFS 从给定源点开始按层次遍历图。在无权图中，BFS 能计算源点到所有可达点的最短路径距离（按跳数计）并判定哪些点可达。

本实现采用基于活动集的迭代式[标签传播](https://en.wikipedia.org/wiki/Label_propagation_algorithm)来实现 BFS。算法流程如下：

1. 将源点的距离设为`0`并标记为已访问；其他点距离为“无穷大”，标记为未访问。
2. 反复从当前活动集进行扩展：对当前活动集中的每个点`u`，遍历其所有邻居`v`。如果邻居`v`还未访问，则执行以下三步：

  1. 将`v`标记为已访问，避免重复处理。
  2. 设置`v`的距离为`distance[u] + 1`（核心逻辑：源点到`v`的路径比到`u`的路径多一步）。
  3. 将`v`加入下一轮的活动集。

3. 当本轮活动集的所有点处理完毕后，用新活动集替换当前活动集并进入下一轮。当新活动集为空时，表示已无更多可达且未访问的点，算法停止。

更多关于 BFS 的信息，请参见[广度优先搜索](https://zh.wikipedia.org/wiki/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2)。

## 数据模型

为了用 GQL 实现 BFS，将基于以下数据模型来创建图类型：

- 用类型为`Person`的点表示人员。
- 用类型为`Knows`的边表示人员之间的关系。

该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/bfs/#1_prepare_graph_data)。

## 过程实现[]()

为计算从单一源点的跳数距离并标记可达性，创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)，以活动集方式实现 BFS。

该过程的完整定义，请参见[创建过程](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/bfs/#2_create_a_procedure)。下文说明过程的关键组件及其工作原理。

过程接收以下输入参数：

- `sid`：源点 ID。

此外，过程内定义以下变量：

 | 变量 | 类型 | 说明
 | `min_distance` | 点绑定 [MinAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/min_agg/) | 每个点的跳数距离。初始化为较大的值（如`999`）；源点设为`0`。MinAgg 确保点保留目前为止的最小距离。
 | `visited` | 点绑定 [OrAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/or_agg/) | 点是否已访问。一旦访问，将保持为`true`。
 | `new_active` | 全局 [OrAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/or_agg/) | 表示本轮是否有新点被访问；用于控制循环终止。
 | `v_set` | [活动集变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | 下一轮需要扩展的点集合。
 | `output_file` | [文件变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/file-variable/) | 用于收集并输出最终结果的文件变量。

过程逻辑如下：

1. 源点初始化：将其`visited`设为`true`、`min_distance`设为`0`，并用源点初始化活动集`v_set`。
2. 

当`new_active`为`true`时重复：

  1. 将`new_active`置为`false`。
  2. 对每条边（`v -> d`），其中`v`属于`v_set`且`d`尚未访问：设置`visited[d] = true`，依据`min_distance[d] = min(min_distance[d], min_distance[v] + 1)`更新`min_distance[d]`的值，并将`new_active`置为`true`。
  3. 将本轮更新到的所有点`d`作为下一轮的活动集`v_set`。

3. 

收敛后（某一轮无更新），将每个点的 ID、`min_distance`与`visited`导出到`output_file`并返回。

## 操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。

### 1. 准备图数据[]()

1. 

创建与数据模型匹配的图类型。

````
'''
CREATE GRAPH TYPE IF NOT EXISTS bfs_graph_type AS {
    NODE Person (LABEL Person {id INT PRIMARY KEY, name STRING}),
    EDGE Knows (Person)-[LABEL Knows {MULTIEDGE KEY ()}]->(Person)
}
'''

````

2. 

下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/bfs/`：

  - [bfs_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/bfs/bfs_node.csv)：点数据。
  - [bfs_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/bfs/bfs_edge.csv)：边数据。

查看 CSV 内容

bfs_node.csv

````
id,name
1,Alice
2,Bob
3,Charlie
4,David

````

bfs_edge.csv

````
src,dst
1,2
2,3
1,4
3,4
4,2

````

3. 

基于图类型创建临时图，并将数据文件加载到该临时图中。

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #bfs_graph TYPED bfs_graph_type

````

````
'''
USE #bfs_graph IMPORT INTO GRAPH {
    NODE (v@Person {id: id, name: name}) FROM DATAFILE {
      PATH: "file:///examples/algorithms/bfs/bfs_node.csv",
      FORMAT: "CSV",
      DELIMITER: ','
    },
    EDGE (id: src)-[e@Knows{}]->(id: dst) FROM DATAFILE {
      PATH: "file:///examples/algorithms/bfs/bfs_edge.csv",
      FORMAT: "CSV",
      DELIMITER: ','
    }
  }
'''

````

导入成功后，在控制台执行以下查询核对点数：

````
'''
USE #bfs_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

`node_count`应为`4`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。

### 2. 创建过程[]()

创建一个过程以实现 BFS 算法。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/bfs/#procedure_implement)。

````
'''
CREATE OR REPLACE PROCEDURE bfs(sid INT64) RETURNS () AS {
    VALUE      v_set        ACTIVE_SET
    VALUE      new_active   OrAgg = true
    NODE VALUE min_distance MinAgg<INT> = 999
    NODE VALUE visited      OrAgg = false
    FILE       output_file  {id INT64, distance INT64, visited BOOL} = DATAFILE {
                                  PATH: "file:///examples/algorithms/bfs/output",
                                  FORMAT: "CSV"
                                  }

    // 初始化源点
    MATCH (s@Person) WHERE s.id = sid
    FINALLY {
        SET v_set = s
    }

    MATCH (s)
    WHERE s IN v_set
    PER NODE (s) {
      SET s.@visited = true
      SET s.@min_distance = 0
    }

    // 迭代直至无更新
    WHILE @new_active = true THEN {
      SET @new_active = false
      MATCH (v)-[e]-(d)
      WHERE d.@visited = false AND v IN v_set
      PER PATH {
        SET d.@visited += true
        SET d.@min_distance += v.@min_distance + 1   // MinAgg 取最小值
        SET @new_active += true                      // OrAgg 只要有更新即为 true
        }
      FINALLY {
        SET v_set = d
        }
    }

    // 收集结果
    MATCH (s)
    PER NODE (s) {
      EXPORT s.id, s.@min_distance, s.@visited INTO output_file
    }
}
'''

````

### 3. 调用过程

计算从源点`1`出发的跳数距离。

````
USE #bfs_graph CALL bfs(1) FINISH

````

此调用将结果写入 CSV，控制台不返回结果表。

在宿主机的部署目录下，打开`examples/algorithms/bfs/output/`中的 CSV 文件。示例内容如下：

````
"id","distance","visited"
1,0,true
2,1,true
3,2,true
4,1,true

````

将结果写入图中

如果希望将 BFS 结果持久化到图，而不仅导出到文件，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)：

- 先将 BFS 输出字段导出到表变量（通常为`id`、`distance`、`visited`）。
- 若写入远程图，使用`table_split(...)`分批，并通过`nebula_exec`批量执行`USE + INSERT`语句。

执行前，请先设计目标图类型，例如在`Person`上增加`distance`、`visited`属性。