查找图是否有周期 [英] Find whether graph has a cycle

问题描述

我想确定是否可以使用SQL在Hierarchical或Chain数据中找到循环.

I want to find out whether it is possible to find cycles in Hierarchical or Chain data with SQL.

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

E.g. I have following schema: 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的记录属于一个图.

In graph table records with same ID belong to one graph.

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

I need a query that will return IDs of all graphs that have at least one cycle.

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

So for example above query should return 1, which is the id of the first graph;

推荐答案

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

First, I assume this is a directed graph. An undirected graph has a trivial cycle if it contains a single edge.

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

The only tricky part to the recursive CTE is stopping when you've hit a cycle -- so you don't get infinite recursion.

尝试一下:

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;

这篇关于查找图是否有周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！