Demonstrates the use of a recursive CTE to find the neighbors of a vertex through its edges in a PostgreSQL database.

undirected_graph.sql

-- https://www.postgresql.org/docs/current/queries-with.html

DROP TABLE IF EXISTS vertex;
DROP TABLE IF EXISTS edge;

CREATE TABLE IF NOT EXISTS vertex (
    id int primary key
);

CREATE TABLE IF NOT EXISTS  edge (
    source int,
    target int,
    primary key (source, target),
    -- prevent duplicates and self-loop
    check ( source < target )
);

INSERT INTO vertex (id) VALUES (1);
INSERT INTO vertex (id) VALUES (2);
INSERT INTO vertex (id) VALUES (3);
INSERT INTO vertex (id) VALUES (4);
INSERT INTO vertex (id) VALUES (5);
INSERT INTO vertex (id) VALUES (6);

INSERT INTO edge (source, target) VALUES (1,2);
INSERT INTO edge (source, target) VALUES (2,3);
INSERT INTO edge (source, target) VALUES (3,4);
INSERT INTO edge (source, target) VALUES (4,5);
INSERT INTO edge (source, target) VALUES (5,6);

-- select the neighbors with breadth-first search
WITH RECURSIVE neighbors(id, source, target, depth, is_cycle, path) AS (
    SELECT v.id, e.source, e.target, 3, false, ARRAY[v.id]
    FROM vertex v
    INNER JOIN edge e ON v.id IN (e.source, e.target)
    WHERE v.id = 3
    UNION ALL
    SELECT v.id, e.source, e.target, n.depth - 1, v.id = ANY(path), path || v.id
    FROM vertex v
    INNER JOIN edge e ON v.id IN(e.source, e.target)
    INNER JOIN neighbors n ON v.id IN (n.source, n.target)
    WHERE n.depth > 0 AND NOT n.is_cycle
)
SELECT *
FROM neighbors n
WHERE NOT n.is_cycle
ORDER BY n.depth DESC