如何使用SQL计算源节点与目标节点间的跳数/停靠次数？

问题背景 #

我有一张包含source（源）和destination（目标）两列的表，数据如下：

我需要计算从源s1到目标f1、源s2到目标f2之间的停靠次数。举个例子：

• s1到f1之间有3个停靠点
• s2到f2之间有4个停靠点

我平时常用SQL做常规查询，但从没处理过这类路径遍历的问题，请问该怎么写对应的SQL？

解决方案 #

这是典型的树形路径遍历问题，用SQL的**递归公共表表达式（CTE）**就能完美解决——这是处理层级/链式数据的标准方案，我给你拆解一下实现思路：

核心思路 #

递归CTE分为两部分：

1. 锚点成员：先定义路径的起始节点（也就是你的s1、s2），同时初始化停靠次数的计数
2. 递归成员：不断把当前节点的下一个目标节点连进来，每走一步就把停靠次数加1，直到到达终点（f1、f2）

针对你的场景的SQL代码 #

假设表名叫route_table，先给你写一个贴合你具体数据的版本：

WITH RECURSIVE route_traversal AS (
    -- 第一步：锚点，从指定的起始源开始
    SELECT 
        source AS current_node,
        destination AS next_node,
        1 AS stop_count  -- 第一个节点d1/d3算第一次停靠
    FROM route_table
    WHERE source IN ('s1', 's2')
    
    UNION ALL
    
    -- 第二步：递归遍历后续节点，直到终点
    SELECT 
        rt.next_node AS current_node,
        rt2.destination AS next_node,
        rt.stop_count + 1 AS stop_count
    FROM route_traversal rt
    JOIN route_table rt2 ON rt.next_node = rt2.source
    -- 还没到终点的时候继续递归
    WHERE rt2.destination NOT IN ('f1', 'f2')
)
-- 最后筛选到达终点的记录，计算总停靠次数
SELECT 
    -- 匹配对应的起始源
    CASE 
        WHEN current_node = 'd2' THEN 's1'
        WHEN current_node = 'd5' THEN 's2'
    END AS source,
    next_node AS destination,
    stop_count + 1 AS total_stops  -- 加上终点f1/f2的那次停靠
FROM route_traversal
WHERE next_node IN ('f1', 'f2');

更通用的版本（无需硬编码节点） #

如果你的数据里，起始节点是从未出现在destination列的节点，终点是从未出现在source列的节点，可以用这个通用版，不用每次改硬编码的节点名：

WITH RECURSIVE route_traversal AS (
    -- 自动识别所有起始节点（没有被任何节点指向的节点）
    SELECT 
        source AS start_node,
        source AS current_node,
        destination AS next_node,
        1 AS stop_count
    FROM route_table
    WHERE source NOT IN (SELECT DISTINCT destination FROM route_table)
    
    UNION ALL
    
    -- 递归遍历路径
    SELECT 
        rt.start_node,
        rt.next_node AS current_node,
        rt2.destination AS next_node,
        rt.stop_count + 1 AS stop_count
    FROM route_traversal rt
    JOIN route_table rt2 ON rt.next_node = rt2.source
    -- 还没到终点（当前节点的下一个节点还有后续）就继续
    WHERE rt2.source IN (SELECT DISTINCT source FROM route_table)
)
-- 筛选出到达终点的记录，输出结果
SELECT 
    start_node AS source,
    next_node AS destination,
    stop_count AS total_stops
FROM route_traversal
-- 终点是没有后续节点的节点
WHERE next_node NOT IN (SELECT DISTINCT source FROM route_table);

运行结果 #

不管用哪个版本，最终都会得到你想要的结果：

关键点说明 #

• 递归CTE的工作原理：先执行锚点查询得到初始结果，然后反复执行递归部分，把新的结果和之前的合并，直到没有新的记录产生
• 停靠次数的计数逻辑：你的例子里，s1到f1的路径是s1→d1→d2→f1，从s1之后的第一个节点开始算，到f1一共3个节点，所以计数是3——递归过程中每走一步加1，最后正好对应这个数

内容的提问来源于stack exchange，提问作者Metadata