主页 / coding / 问题 / 79566547
Accepted
David Kerr
Asked: 2025-04-10 19:42:59 +0800 CST

使用递归 CTE 遍历图形 - 使用“数组”存储访问过的顶点

  • 772

我正在学习使用递归 CTE 进行图遍历（learnSQL 课程）。题目问的是从一个起始城市访问每个城市。他们使用一个由附加城市名称构建的“路径”字符串，然后用它来where position(city.name IN travel.path) = 0判断该城市是否已经被访问过。这种方法可行，但我经常寻找替代方案，所以我可以使用一个已访问城市数组。

作为一名经验丰富的开发人员（例如 Java 或任何命令式语言），我会将其表示visited为 SET 以进行有效的遏制测试，但 postgresql 似乎只提供 ARRAY。

  1. 是否有我可以使用的 SET 类型（简单的类型，而不是单独的表或 JSON 集）？
  2. ARRAY 在查找方面是否高效？

当然，示例数据很小，这没什么问题，但我想知道最有效/最佳实践是什么。在我看来，使用字符串查找语义position不太好。

谢谢！

with recursive
travel(path, visited, visited_count) AS (
  select
    name::text,
    array[name::text],
    1
  
  from city
  where
    name = 'Bristol'
  
  union all
  
  select
    travel.path || '->' || city.name,
    visited || name::text,
    visited_count + 1
  
  from city, travel
  
  where
    city.name <> all(visited)
    --position(city.name IN travel.path) = 0
)
  
select
  path,
  visited

from travel

where
  visited_count = 6
postgresql

1 个回答

  1. Best Answer

    使用该ARRAY方法是为了语义清晰，因为数组检查（<> ALL）和字符串搜索（position()）在递归步骤中具有类似的 O(N) 查找性能。

    WITH RECURSIVE travel(path, visited, visited_count) AS (
  -- base case
  SELECT name::text, ARRAY[name::text], 1
  FROM city WHERE name = 'Bristol'

  UNION ALL

  -- recursive step
  SELECT
    t.path || '->' || c.name, -- build path string
    t.visited || c.name::text, -- append to visited array (o(n) copy + append)
    t.visited_count + 1
  FROM city c, travel t
  WHERE c.name <> ALL(t.visited) -- check if visited (o(n) array scan)
)
SELECT path, visited
FROM travel
WHERE visited_count = (SELECT count(*) FROM city); -- condition to stop (e.g., all cities visited)
    • 0

相关问题