4. 递归CTE实现广度优先遍历（BFS）

广度优先遍历，说白了就是一层一层往外扫。在反欺诈图谱里，我常用它来算“两个账号之间隔了几层”、“风险能从源头传染到多远”。递归CTE默认走的是深度优先（DFS），但我们可以手动改成BFS。今天我们就聊聊怎么改，以及为什么在反欺诈场景下BFS比DFS更好用。

4.1 为什么反欺诈更需要BFS

回想一下DFS的习性：一条路走到黑，撞墙再回头。这在路径查找上没问题，但遇到要统计“距离起点X层以内的所有节点”时就尴尬了。比如查二度关系，DFS可能先钻进一个长长的链，绕半天才回来扫第二层。而BFS按层推进，一视同仁。

我几年前接手过一个团伙识别项目。数据里有一个核心欺诈账号，周围挂了上万个成员。用DFS递归查二度关系，跑了三分钟还没结果。换成BFS，十秒出数据。你想想看，性能差距就是这么大。

4.2 递归CTE的BFS改造方法

标准递归CTE长这样：

WITH RECURSIVE path AS (
  -- 锚点
  SELECT id, 1 AS depth
  FROM nodes
  WHERE id = 'start'

  UNION ALL

  -- 递归部分
  SELECT n.id, p.depth + 1
  FROM path p
  JOIN edges e ON p.id = e.src
  JOIN nodes n ON e.dst = n.id
  WHERE p.depth < 3   -- 限制层数
)
SELECT * FROM path;

问题出在哪？递归CTE默认以深度优先顺序生成结果。同一层的节点可能分散在整个执行过程中。虽然最终结果一样，但如果你想在每层结束时做聚合（比如计数、求平均），就不好做了。

怎么改成BFS？其实只需在递归部分加上排序方向控制。PG官方在9.4之后引入了SEARCH BREADTH FIRST BY子句，直接指定按深度排序即可：

WITH RECURSIVE bfs AS (
  SELECT 
    id,
    name,
    0 AS depth,
    ARRAY[id] AS path
  FROM nodes
  WHERE id = 'A001'

  UNION ALL

  SELECT 
    n.id,
    n.name,
    b.depth + 1,
    b.path || n.id
  FROM bfs b
  JOIN edges e ON b.id = e.src
  JOIN nodes n ON e.dst = n.id
  WHERE b.depth < 2
    AND NOT n.id = ANY(b.path)  -- 防止回路
)
SEARCH BREADTH FIRST BY depth SET order_col
SELECT id, depth, name
FROM bfs
ORDER BY order_col;

注意最后多了SEARCH BREADTH FIRST BY depth SET order_col。这行会把同深度的节点排在一起，并生成一个隐式的order_col列用于外部排序。实际查询时再ORDER BY order_col，就能保证输出是BFS顺序。

4.3 实战：二度关系团伙检测

反欺诈里最经典的场景是查“某账号的二度联系人”。比如有账号A转账给B，B又转账给C，那么A和C就是二度关系。用BFS实现：

WITH RECURSIVE bfs AS (
  -- 起点：目标账号
  SELECT 
    account_id AS start_id,
    account_id AS node_id,
    0 AS depth
  FROM accounts
  WHERE account_id = 'TARGET001'

  UNION ALL

  SELECT 
    b.start_id,
    t.target_id AS node_id,
    b.depth + 1
  FROM bfs b
  JOIN transactions t 
    ON t.source_id = b.node_id  -- 从当前节点出发的交易
  WHERE b.depth < 2
    AND t.target_id != b.node_id  -- 排除自环
)
SEARCH BREADTH FIRST BY depth SET order_col
SELECT 
  node_id,
  depth,
  CASE 
    WHEN depth = 0 THEN '起点'
    WHEN depth = 1 THEN '一度关系'
    WHEN depth = 2 THEN '二度关系'
  END AS relation_type
FROM bfs
ORDER BY order_col;

这个查询返回所有一度、二度的节点。我拿它去做过团伙拉网——先把一个已知坏账号的二度关系网兜住，再往里灌入交易频次、金额异动等特征，准确率能提高20%以上。

4.4 BFS与DFS的对比表格

特性	BFS（广度优先）	DFS（深度优先）
遍历顺序	先处理同一层所有节点	一条路径走到叶节点再回溯
适合场景	层数有限、需要按层统计	路径查找、拓扑排序
SQL实现难度	需SEARCH子句或额外排序	标准递归CTE默认
反欺诈典型用法	二度/三度关系检测	资金流向追踪
内存消耗	队列存储同层节点，层数多时较大	栈存储递归深度，深度大时可能爆栈

说实话，反欺诈图谱里BFS用得比DFS多得多。因为大多数业务场景都是“查周围X层”，而不是“查最深那条链”。我建议你把BFS作为日常首选，DFS留着处理资金流向追踪那种特殊需求。

4.5 BFS遍历流程示意图

4.6 避坑指南

• 回路问题：图里很可能出现A→B→A的回路。不加限制的话递归CTE会无限循环。我习惯用path数组记录已访问节点，并在递归条件里加上NOT node_id = ANY(path)。
• 性能调优：BFS在同层节点很多时，连接次数呈指数增长。我建议加上depth < N的硬限制，同时给join列建索引（比如edges表的src、dst字段）。
• 数据库兼容性：PostgreSQL、SQL Server支持SEARCH BREADTH FIRST；MySQL 8.0虽然支持递归CTE但不支持该子句，需要用外部排序兜底。Oracle和DB2也有各自写法，升级前先检查文档。

嗯，BFS这部分其实不难，关键是要理解它“逐层递进”的本质。下次碰到需要算“几度朋友”或者“风险传染层级”的需求，你直接递归CTE套BFS模式，十有八九能拿下。