Muster
Einen Graphen ohne Schleifen durchlaufen
Eine rekursive Abfrage über Verbindungen, die Schleifen bilden können, muss ihren Pfad mitführen und das erneute Besuchen eines Knotens verweigern.
Eine Hierarchie hat keine Schleifen, ein Graph von Verbindungen (geteilte Karten, Empfehlungen, Freundschaften)
schon. Führen Sie den Pfad als Text mit (',1,', dann path || next || ',') und fügen Sie dem rekursiven Schritt
WHERE path NOT LIKE '%,' || next || ',%' hinzu: Ein Knoten, der schon auf dem Pfad liegt, wird nicht erneut besucht.
Die Kommas um jede ID verhindern, dass 1 auf 12 passt. Das funktioniert auf jeder Engine; Arrays leisten dasselbe, wo
es sie gibt (<> ALL(path) in Postgres, NOT IN UNNEST(path) in BigQuery). Begrenzen Sie bei echten Daten die Tiefe, da
die Zahl der Pfade schnell wächst, und behalten Sie am Ende die kleinste Distanz pro Knoten.
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 |