广度优先搜索（BFS）¶

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

算法简介¶

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

本实现采用基于活动集的迭代式标签传播来实现 BFS。算法流程如下：

将源点的距离设为0并标记为已访问；其他点距离为“无穷大”，标记为未访问。
反复从当前活动集进行扩展：对当前活动集中的每个点u，遍历其所有邻居v。如果邻居v还未访问，则执行以下三步：
1. 将v标记为已访问，避免重复处理。
2. 设置v的距离为distance[u] + 1（核心逻辑：源点到v的路径比到u的路径多一步）。
3. 将v加入下一轮的活动集。
当本轮活动集的所有点处理完毕后，用新活动集替换当前活动集并进入下一轮。当新活动集为空时，表示已无更多可达且未访问的点，算法停止。

更多关于 BFS 的信息，请参见广度优先搜索。

数据模型¶

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

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

该图类型的完整定义，请参见准备图数据。

过程实现 ¶

为计算从单一源点的跳数距离并标记可达性，创建一个过程，以活动集方式实现 BFS。

该过程的完整定义，请参见创建过程。下文说明过程的关键组件及其工作原理。

过程接收以下输入参数：

sid：源点 ID。

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

变量	类型	说明
`min_distance`	点绑定 MinAgg 聚合值变量	每个点的跳数距离。初始化为较大的值（如`999`）；源点设为`0`。MinAgg 确保点保留目前为止的最小距离。
`visited`	点绑定 OrAgg 聚合值变量	点是否已访问。一旦访问，将保持为`true`。
`new_active`	全局 OrAgg 聚合值变量	表示本轮是否有新点被访问；用于控制循环终止。
`v_set`	活动集变量	下一轮需要扩展的点集合。
`output_file`	文件变量	用于收集并输出最终结果的文件变量。

过程逻辑如下：

源点初始化：将其visited设为true、min_distance设为0，并用源点初始化活动集v_set。
当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。
收敛后（某一轮无更新），将每个点的 ID、min_distance与visited导出到output_file并返回。

操作步骤¶

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按准备算法示例数据确认操作位置和目录挂载。

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)
}
'''

下载以下 CSV 文件，保留文件名，保存到部署目录下的examples/algorithms/bfs/：
- bfs_node.csv：点数据。
- 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
```

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

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。点数不符时，先按文件问题排查检查文件和导入结果。

2. 创建过程 ¶

创建一个过程以实现 BFS 算法。关于该过程的更多信息，请参见过程实现。

'''
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：

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

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