sql - 拓扑排序的 SQL 查询

Question

我有一个有向无环图：

DROP TABLE IF EXISTS #Edges
CREATE TABLE #Edges(from_node int, to_node int);
INSERT INTO #Edges VALUES (1,2),(1,3),(1,4),(5,1);

我想列出所有节点，总是在它的 from 节点之前列出一个 to 节点。例如：2、3、4、1、5。

它也称为拓扑排序。如何在 SQL 中完成？

标签： sqlsql-servergraph-algorithmgraph-traversaltopological-sort

Answer 1

您可以使用递归 CTE 来计算深度。然后按深度排序：

with cte as (
      select e.from_node, e.to_node, 1 as lev
      from edges e
      where not exists (select 1 from edges e2 where e2.to_node = e.from_node)
      union all
      select e.from_node, e.to_node, lev + 1
      from cte join
           edges e
           on e.from_node = cte.to_node
     )
select *
from cte
order by lev desc;

编辑：

我注意到您的边缘列表中没有“1”。要处理这个：

with cte as (
      select 1 as from_node, e.from_node as to_node, 1 as lev
      from edges e
      where not exists (select 1 from edges e2 where e2.to_node = e.from_node)
      union all
      select e.from_node, e.to_node, lev + 1
      from cte join
           edges e
           on e.from_node = cte.to_node
      -- where lev < 5
     )
select *
from cte
order by lev desc;

这是一个 db<>fiddle。