递归CTE实现有向无环图的拓扑排序与路径枚举

超越常见的斐波那契数列案例，使用递归公用表表达式（CTE）对DAG进行拓扑排序，并枚举所有从根节点到叶节点的路径。 · 难度：入门 · +10XP

递归CTE实现有向无环图的拓扑排序与路径枚举

递归CTE常用于处理树形结构，但也可以处理更复杂的图。本教程通过一个有向无环图（DAG）的任务依赖表，演示如何用递归CTE计算拓扑排序，同时收集从起始节点到目标节点的所有路径（包括路径字符串拼接）。关键技术包括锚点成员、递归成员、UNION ALL以及层级控制。

-- 任务依赖表
CREATE TABLE task_dependencies (
    task_id INT,
    depends_on INT
);
-- 插入数据：1依赖2和3，2依赖4
-- 递归CTE枚举所有路径
WITH RECURSIVE paths AS (
    SELECT task_id, CAST(task_id AS CHAR(200)) AS path, 1 AS depth
    FROM tasks WHERE task_id NOT IN (SELECT depends_on FROM task_dependencies)
    UNION ALL
    SELECT t.task_id, CONCAT(p.path, '->', t.task_id), p.depth+1
    FROM tasks t
    JOIN paths p ON t.depends_on = p.task_id
)
SELECT * FROM paths ORDER BY depth, task_id;