Início / coding / Perguntas / 79566547
Accepted
David Kerr
Asked: 2025-04-10 19:42:59 +0800 CST

Percorrendo um gráfico usando CTE recursivo - usando "array" para armazenar vértices visitados

  • 772

Estou estudando travessia de grafos usando CTEs recursivas (curso learnSQL). A questão pergunta sobre visitar cada cidade a partir de uma cidade inicial. Eles usam uma string "path" construída a partir de nomes de cidades anexados e, em seguida, usam where position(city.name IN travel.path) = 0para verificar se a cidade já foi visitada. Isso funciona, mas costumo procurar alternativas e poderia usar um array de cidades visitadas.

Como um desenvolvedor experiente (por exemplo, Java, mas qualquer linguagem imperativa), eu representaria visitedcomo um SET para testes de contenção eficientes, mas o postgresql parece oferecer apenas ARRAY.

  1. Existe um tipo SET (algo simples, não uma tabela separada ou conjunto JSON) que eu possa usar?
  2. O ARRAY é eficiente em termos de pesquisa?

Os dados de exemplo são, claro, minúsculos e não representam um problema, mas gostaria de saber o que é mais eficiente/melhor prática. Na minha opinião, a consulta por string positionnão é muito semântica .

Obrigado!

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 respostas

  1. Best Answer

    Use a ARRAYabordagem para clareza semântica, pois tanto as verificações de matriz ( <> ALL) quanto as pesquisas de string (position()) têm desempenho de pesquisa O(N) semelhante dentro da etapa recursiva.

    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

relate perguntas