Tecnica

Percorrere un grafo senza girare in tondo

Una query ricorsiva su collegamenti che possono formare cicli deve portarsi dietro il percorso e rifiutarsi di rivisitare un nodo.

Una gerarchia non ha cicli, un grafo di collegamenti (carte condivise, referral, amicizie) sì. Porta il percorso come testo (',1,', poi path || next || ',') e aggiungi WHERE path NOT LIKE '%,' || next || ',%' al passo ricorsivo: un nodo già sul percorso non viene rivisitato. Le virgole attorno a ogni id impediscono a 1 di corrispondere a 12. Funziona su ogni motore; gli array fanno lo stesso dove esistono (<> ALL(path) su Postgres, NOT IN UNNEST(path) su BigQuery). Limita la profondità sui dati reali, perché il numero di percorsi cresce in fretta, e alla fine tieni la distanza minima per 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

Provalo in Randori

Esercitati:Linked through a shared card