Technique

Parcourir un graphe sans boucler

Une requête récursive sur des liens qui peuvent boucler doit porter son chemin et refuser de repasser par un nœud.

Une hiérarchie n'a pas de boucle, un graphe de liens (cartes partagées, parrainages, amitiés) en a. Portez le chemin sous forme de texte (',1,', puis chemin || suivant || ',') et ajoutez WHERE chemin NOT LIKE '%,' || suivant || ',%' à l'étape récursive : un nœud déjà sur le chemin n'est pas revisité. Les virgules autour de chaque id empêchent 1 de correspondre à 12. Cela marche sur tous les moteurs ; les tableaux font de même là où ils existent (<> ALL(chemin) sur Postgres, NOT IN UNNEST(chemin) sur BigQuery). Plafonnez la profondeur sur de vraies données, car le nombre de chemins grossit vite, et gardez la plus petite distance par nœud à la fin.

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

L’essayer en Randori

Pratiquer :Reliés par une carte partagée