SQL 查询拓扑排序
SQL query for topological sort
我有一个有向无环图:
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);
我想列出所有节点,始终在其起始节点之前列出终止节点。
例如:2、3、4、1、5。
也叫拓扑排序。如何在 SQL 中完成?
您可以使用递归 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;
Here 是一个 db<>fiddle.
DROP TABLE IF EXISTS #topological_sorted
CREATE TABLE #topological_sorted(id int identity(1,1) primary key, n int);
WITH rcte(n) AS (
SELECT e1.to_node
FROM #Edges AS e1
LEFT JOIN #Edges AS e2 ON e1.to_node = e2.from_node
WHERE e2.from_node IS NULL
UNION ALL
SELECT e.from_node
FROM #Edges AS e
JOIN rcte ON e.to_node = rcte.n
)
INSERT INTO #topological_sorted(n)
SELECT *
FROM rcte;
SELECT * FROM #topological_sorted
节点可能会被多次列出。我们只想保留第一次出现:
DROP TABLE IF EXISTS #topological_sorted_2
SELECT *, MIN(id) OVER (PARTITION BY n) AS idm
INTO #topological_sorted_2
FROM #topological_sorted
ORDER BY id;
SELECT * FROM #topological_sorted_2
WHERE id=idm
ORDER BY id;
我有一个有向无环图:
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);
我想列出所有节点,始终在其起始节点之前列出终止节点。 例如:2、3、4、1、5。
也叫拓扑排序。如何在 SQL 中完成?
您可以使用递归 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;
Here 是一个 db<>fiddle.
DROP TABLE IF EXISTS #topological_sorted
CREATE TABLE #topological_sorted(id int identity(1,1) primary key, n int);
WITH rcte(n) AS (
SELECT e1.to_node
FROM #Edges AS e1
LEFT JOIN #Edges AS e2 ON e1.to_node = e2.from_node
WHERE e2.from_node IS NULL
UNION ALL
SELECT e.from_node
FROM #Edges AS e
JOIN rcte ON e.to_node = rcte.n
)
INSERT INTO #topological_sorted(n)
SELECT *
FROM rcte;
SELECT * FROM #topological_sorted
节点可能会被多次列出。我们只想保留第一次出现:
DROP TABLE IF EXISTS #topological_sorted_2
SELECT *, MIN(id) OVER (PARTITION BY n) AS idm
INTO #topological_sorted_2
FROM #topological_sorted
ORDER BY id;
SELECT * FROM #topological_sorted_2
WHERE id=idm
ORDER BY id;