Técnica

Recorrer un grafo sin dar vueltas

Una consulta recursiva sobre enlaces que pueden formar bucles debe llevar su camino y negarse a volver a visitar un nodo.

Una jerarquía no tiene bucles; un grafo de enlaces (tarjetas compartidas, recomendaciones, amistades) sí. Lleve el camino como texto (',1,' y luego path || next || ',') y añada WHERE path NOT LIKE '%,' || next || ',%' al paso recursivo: un nodo que ya está en el camino no se vuelve a visitar. Las comas alrededor de cada id evitan que 1 coincida con 12. Funciona en todos los motores; los arrays hacen lo mismo donde existen (<> ALL(path) en Postgres, NOT IN UNNEST(path) en BigQuery). Limite la profundidad con datos reales, porque el número de caminos crece rápido, y quédese al final con la distancia mínima por nodo.

WITH RECURSIVE links(a, b) AS (VALUES (1, 2), (2, 1), (2, 3), (3, 2), (3, 1), (1, 3), (3, 4), (4, 3)),
walk AS (
  SELECT 1 AS node, 0 AS distance, CAST(',1,' AS VARCHAR) AS path
  UNION ALL
  SELECT l.b, w.distance + 1, w.path || CAST(l.b AS VARCHAR) || ','
  FROM walk w
  JOIN links l ON l.a = w.node
  WHERE w.path NOT LIKE '%,' || CAST(l.b AS VARCHAR) || ',%'
)
SELECT node, MIN(distance) AS distance
FROM walk
WHERE node <> 1
GROUP BY node
ORDER BY node;

node	distance
2	1
3	1
4	2

Probarlo en Randori

Practicar:Linked through a shared card