PostgreSQL递归CTE实现河网上游遍历：按最大area属性选择岔路方向

问题背景 #

需要在河网拓扑图中沿上游方向遍历路径，直至到达终端节点。上游遍历时会遇到支流交汇的岔口，存在多条可选路径，需通过河段的area属性指定遍历方向，始终选择area值最大的河段前进，基于PostgreSQL递归CTE实现该功能。

河网示意图 #

红色为河段、蓝色为节点。

测试数据构造 #

CREATE TEMP TABLE tree (
  id_reach integer PRIMARY KEY,
  from_node integer UNIQUE NOT NULL,
  to_node integer,
  area float
);

INSERT INTO tree(id_reach, from_node, to_node, area) VALUES
 (0, 1, 0, 40),
 (1, 3, 1, 29),
 (2, 2, 1, 5),
 (3, 4, 3, 7),
 (4, 5, 3, 6); 

需求说明 #

指定图中任意节点作为起点，向上游遍历时始终选择area值最大的河段前进，预期输出如下：

starting node |  path  |
---------------+---------
       0        {0, 1, 3}
       1        {1, 3}
       3        {3}

现有实现问题 #

原有递归CTE未加入最大area筛选逻辑，会返回起点上游所有河段：

WITH RECURSIVE us_path AS (
    SELECT id_reach,
        from_node,
        to_node
    FROM tree
    WHERE to_node = 1
    UNION ALL
    SELECT tr.id_reach,
        tr.from_node,
        tr.to_node
    FROM tree as tr
        JOIN us_path AS usp ON tr.to_node = usp.from_node
)
SELECT id_reach
FROM us_path;

返回结果为所有上游河段ID：1、2、3、4，不符合需求。

解决方案 #

单起点查询 #

以查询起点为0的路径为例：

WITH RECURSIVE us_path AS (
    -- 锚点：取起点对应上游area最大的河段
    SELECT 
        id_reach,
        from_node,
        ARRAY[id_reach] AS path
    FROM tree
    WHERE to_node = 0 -- 替换为目标起点节点
    ORDER BY area DESC
    LIMIT 1
    UNION ALL
    -- 递归：每次仅取当前节点上游area最大的河段
    SELECT 
        tr.id_reach,
        tr.from_node,
        usp.path || tr.id_reach AS path
    FROM tree tr
    JOIN us_path usp ON tr.to_node = usp.from_node
    ORDER BY tr.area DESC
    LIMIT 1
)
-- 取最长路径即为完整遍历结果
SELECT 
    (SELECT to_node FROM tree WHERE id_reach = path[1]) AS starting_node,
    path
FROM us_path
ORDER BY array_length(path, 1) DESC
LIMIT 1;

多起点批量查询 #

可一次性返回多个起点的遍历结果：

WITH start_nodes(node) AS (
    VALUES (0), (1), (3) -- 要查询的所有起点
),
node_path AS (
    SELECT 
        s.node AS starting_node,
        (
            WITH RECURSIVE us_path AS (
                SELECT id_reach, from_node, ARRAY[id_reach] AS path
                FROM tree
                WHERE to_node = s.node
                ORDER BY area DESC LIMIT 1
                UNION ALL
                SELECT tr.id_reach, tr.from_node, usp.path || tr.id_reach
                FROM tree tr
                JOIN us_path usp ON tr.to_node = usp.from_node
                ORDER BY tr.area DESC LIMIT 1
            )
            SELECT path FROM us_path ORDER BY array_length(path,1) DESC LIMIT 1
        ) AS path
    FROM start_nodes s
)
SELECT * FROM node_path;

实现逻辑说明 #

• 递归的每一步通过ORDER BY area DESC LIMIT 1仅保留area最大的上游河段，避免返回所有支流路径
• 用数组累计遍历的河段ID，最终取长度最长的数组即为完整的遍历路径，和需求预期完全一致

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