有向图中的sql检测循环

Question

我们有一个由边表表示的有向图。我们如何检测纯 SQL 中的循环？

CREATE TABLE edges(id integer primary key identity, from_node int, to_node int);
CREATE NONCLUSTERED INDEX index_edges_of2 ON edges(from_node);

INSERT INTO edges(from_node,to_node) VALUES(1,2),(2,3),(3,1);

Answer 1

对此的解决方案是递归 CTE。但是，要使其工作，您需要保留一个已访问节点的列表。 SQL Server 没有对此(例如数组)的优雅解决方案，因此您需要使用字符串操作。

下面将列出图中的循环:

with cte as (
      select from_node, to_node, 
             convert(varchar(max), concat(',', from_node, ',', to_node, ',')) as nodes, 1 as lev, 
             (case when from_node = to_node then 1 else 0 end) as has_cycle
      from edges e
      union all
      select cte.from_node, e.to_node,
             convert(varchar(max), concat(cte.nodes, e.to_node, ',')), lev + 1,
             (case when cte.nodes like concat('%,', e.to_node, ',%') then 1 else 0 end) as has_cycle
      from cte join
           edges e
           on e.from_node = cte.to_node
      where cte.has_cycle = 0 
     )
select *
from cte
where has_cycle = 1;

Here是 db<> fiddle 。