查找图是否有周期

admin

查找图是否有周期

sql

我想找出是否有可能使用SQL在Hierarchical或Chain数据中找到循环。

例如，我有以下架构：http :
//sqlfiddle.com/#!3/27269

create table node (
  id INTEGER
 );

create table edges (
   id INTEGER,
   node_a INTEGER,
   node_b INTEGER
);

create table graph (
  id INTEGER,
  edge_id INTEGER);

INSERT INTO node VALUES (1) , (2), (3), (4);
INSERT INTO edges VALUES (1, 1, 2), (2, 2, 3) , (3, 3, 4) , (4, 4, 1);
-- first graph [id = 1] with cycle (1 -> 2 -> 3 -> 4 -> 1)
INSERT INTO graph VALUES (1, 1), (1, 2), (1, 3), (1, 4); 
-- second graph [id =2] without cycle (1 -> 2 -> 3)
INSERT INTO graph VALUES (2, 1), (2, 2), (2, 3);

在graph表中，具有相同ID的记录属于一个图。

我需要一个查询，该查询将返回至少有一个周期的所有图的ID。

因此，例如，上面的查询应返回1，这是第一个图的ID；

阅读 151

2021-07-01

共1个答案

admin

首先，我假设这是一个有向图。如果无向图包含单个边，则其周期很短。

递归CTE唯一棘手的部分是在遇到周期时停止-因此您不会得到无限递归。

试试这个：

with cte as (
      select e.object_a, e.object_b, iscycle = 0
      from edges e
      union all
      select cte.object_a, e.object_b,
             (case when cte.object_a = e.object_b then 1 else 0 end) as iscycle
      from cte join
           edges e
           on cte.object_b = e.object_a
      where iscycle = 0
     )
select max(iscycle)
from cte;

2021-07-01