我的PostgreSQL数据库中有一个有向图,节点和循环之间可以有多个路径:
create table "edges" ("from" int, "to" int);
insert into "edges" values (0, 1), (1, 2), (2, 3), (3, 4), (1, 3);
insert into "edges" values (10, 11), (11, 12), (12, 11);
我想找到一个节点和与其连接的每个节点之间的最小边数:
with recursive "nodes" ("node", "depth") as (
select 0, 0
union
select "to", "depth" + 1
from "edges", "nodes"
where "from" = "node"
) select * from "nodes";
返回所有路径的深度:
node 0 1 2 3 3 4 4
depth 0 1 2 2 3 3 4
0 -> 1 -> 2 -> 3 -> 4
0 -> 1 ------> 3 -> 4
我需要最少的内容,但是递归查询的递归项中不允许使用聚合函数
with recursive "nodes" ("node", "depth") as (
select 0, 0
union
select "to", min("depth") + 1
from "edges", "nodes"
where "from" = "node"
group by "to"
) select * from "nodes";
在结果上使用聚合函数可以:
with recursive "nodes" ("node", "depth") as (
select 0, 0
union all
select "to", "depth" + 1
from "edges", "nodes"
where "from" = "node"
) select * from (select "node", min("depth")
from "nodes" group by "node") as n;
预期回报
node 0 1 2 3 4
depth 0 1 2 2 3
但是,进入循环会导致无限循环,并且对查询“节点”的递归引用一定不能出现在子查询中,因此我无法检查是否已访问节点:
with recursive "nodes" ("node", "depth") as (
select 10, 0
union
select "to", "depth" + 1
from "edges", "nodes"
where "from" = "node"
and "to" not in (select "node" from "nodes")
) select * from "nodes";
我在这里寻找的结果是
node 10 11 12
depth 0 1 2
有没有一种方法可以使用递归查询/通用表表达式?
另一种方法是创建一个临时表,迭代添加行,直到用完为止。即呼吸优先搜索。
相关:此答案检查节点是否已包含在路径中并避免循环,但仍无法避免进行不必要的工作,以检查出比已知的最短路径更长的路径,因为它的行为仍像深度优先搜索
您可以根据文档在查询中添加周期检测
with recursive "nodes" ("node", "depth", "path", "cycle") as (
select 10, 0, ARRAY[10], false
union all
select "to", "depth" + 1, path || "to", "to" = ANY(path)
from "edges", "nodes"
where "from" = "node" and not "cycle"
) select * from (select "node", min("depth"), "path", "cycle"
from "nodes" group by "node", "path", "cycle") as n
where not "cycle";
该查询将返回您期望的数据
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句