sql - SQL 中图的多个连通分量

Question

我的 PostgreSQL 数据库中有一个图表，为了举例，让我们这样定义它:

CREATE TABLE nodes (node_id INTEGER);
CREATE TABLE roads (road_id INTEGER, nodes INTEGER[]);
INSERT INTO nodes VALUES (1), (2), (3), (4), (5);
INSERT INTO roads VALUES (1, {1, 2}), (2, {3, 4}));

我想创建返回 connected components 数量的 SQL 查询图中，在这个例子中，数字是 3，因为节点 1/2 是连接的，3/4 也是连接的，而 5 没有连接到任何东西。

我尝试搜索 find&union SQL 中的实现但无济于事，然后我求助于 CTEs但我不能自己做，我在想这样的事情:

WITH RECURSIVE cc(iterator_id, node_id, rank, iterator) AS
(
        SELECT row_number() OVER(), n.node_id, row_number() OVER (), 1 FROM nodes AS n
    UNION ALL
        # Something here that does the magic
)
SELECT
    COUNT(DISTINCT rank) AS no_of_cc
FROM
    cc,
    (SELECT COUNT(*) FROM nodes) AS last_iterator_id
WHERE iterator = last_iterator_id;

在每次迭代中，我们更新 iterator_id <= iterator 的行的排名。我们迭代直到 iterator 等于最大的 iterator_id但我想不出递归部分。

你能帮我算出连通分量的数量吗？

Answer 1

你现在呢？尽管我向您推荐使用 PL/Python 编写存储过程，但后来我还是决定为了好玩而编写该单 SQL 查询。这就是我所做的。我使用了 RECURSIVE CTE。

WITH RECURSIVE graph_search(node_id, connected_to, path, cycle) AS (
        SELECT node_id, connected_to, ARRAY[node_id], false FROM paths
    UNION 
        SELECT p.node_id, p.connected_to, gs.path || p.node_id, p.node_id=ANY(gs.path)
        FROM graph_search gs JOIN paths p ON gs.connected_to = p.node_id AND NOT gs.cycle
 ),
 paths AS (
    SELECT node_id, connected_to
    FROM (
        SELECT n.node_id, unnest(r.nodes) AS connected_to
        FROM nodes n JOIN roads r ON n.node_id = ANY(r.nodes)
    ) sub
    WHERE node_id <> connected_to
 ) 
SELECT count(DISTINCT component)
FROM (
        SELECT node_id,
               array_agg(DISTINCT reachable_node ORDER BY reachable_node) as component
        FROM (
            SELECT node_id, unnest(path) as reachable_node from graph_search 
        ) sub
        GROUP BY node_id
    UNION ALL /*need to append lonely nodes - they are components for themselves*/
        SELECT node_id, ARRAY[node_id]
        FROM nodes
        WHERE node_id NOT IN (SELECT node_id from paths)
) sub;

• 首先，我需要图形本身的不同表示。名为 paths 的普通 CTE 创建包含成对连接节点的双列表。
• 然后我稍微修改了example from PostgreSQL manual所以我有节点列表以及从中可以到达的每个节点。
• 聚合为我提供了图形的组成部分。
• 最后，我计算了不同的组件。