递归CTE图遍历：社交网络中的最短路径与闭环检测

用递归公用表表达式（CTE）实现有向图的无环遍历、最短路径查找以及环形依赖检测。 · 难度：入门 · +10XP

递归CTE图遍历

经典的递归CTE教程往往停留在斐波那契数列或层级菜单，但现实中你需要用它解决图论问题：在社交网络中找两个用户的最短距离（六度分隔），或者在产品依赖表中发现循环引用。本教程将展示如何构建带深度限制的广度优先搜索，并使用CYCLE子句（PostgreSQL）或手动路径追踪来避免无限递归。你还会学到如何用ARRAY收集所有访问过的节点，并在最终结果中只返回最短路径。

WITH RECURSIVE paths AS (
  SELECT start_node, end_node, ARRAY[start_node, end_node] AS nodes, 1 AS depth
  FROM edges WHERE start_node = 'A'
  UNION ALL
  SELECT p.start_node, e.end_node, p.nodes || e.end_node, p.depth+1
  FROM paths p
  JOIN edges e ON p.end_node = e.start_node
  WHERE NOT e.end_node = ANY(p.nodes) AND p.depth < 6
)
SELECT * FROM paths WHERE end_node = 'Z' ORDER BY depth LIMIT 1;