在Snowflake SQL中识别含环图的相关节点边组（解决递归死循环）

需求说明 #

给定包含环的边数据，识别所有连通节点的唯一分组，为每条边分配对应的分组标识。原递归SQL因循环问题无限运行，需提供正确实现方案。

示例输入 #

FROM_NODE | TO_NODE
--------- | -------
A         | B
B         | C
C         | D
D         | C
E         | F
G         | H
H         | G

示例输出 #

FROM_NODE | TO_NODE | GROUP_NAME
--------- | ------- | ----------
A         | B       | 1
B         | C       | 1
C         | D       | 1
D         | C       | 1
E         | F       | 2
G         | H       | 3
H         | G       | 3

（注：原示例输出中D | B为笔误，此处修正为与输入一致）

问题代码分析 #

原递归CTE存在两个核心问题：

1. 初始阶段给每条边都分配独立的Rank()值作为分组ID，同一连通分量的边初始分组就不一致。
2. 递归条件仅通过g.FROM_NODE = e2.TO_NODE关联，未跟踪已访问节点，环的存在会导致递归无限循环，无法终止。

WITH edges as (
    select * from (
        values
            ('A', 'B'),
            ('B', 'C'),
            ('C', 'D'),
            ('D', 'B'),
            ('E', 'F'),
            ('G', 'H'),
            ('H', 'G')
    ) as e (FROM_NODE, TO_NODE)
),

groups (FROM_NODE, TO_NODE, GROUP_NAME) AS (
    SELECT
        e1.FROM_NODE,
        e1.TO_NODE,
        Rank() Over (ORDER BY e1.FROM_NODE) as GROUP_NAME
    FROM edges AS e1
    UNION ALL SELECT
        e2.FROM_NODE,
        e2.TO_NODE,
        g.GROUP_NAME
       FROM edges as e2, groups as g
       WHERE g.FROM_NODE = e2.TO_NODE
)

select * from groups order by GROUP_NAME

正确实现方案 #

通过递归CTE识别连通分量，跟踪已访问节点避免循环，再为每个分量分配唯一分组ID：

WITH edges AS (
    SELECT * FROM (
        VALUES
            ('A', 'B'),
            ('B', 'C'),
            ('C', 'D'),
            ('D', 'C'),
            ('E', 'F'),
            ('G', 'H'),
            ('H', 'G')
    ) AS e(FROM_NODE, TO_NODE)
),
-- 生成所有唯一节点集合
nodes AS (
    SELECT FROM_NODE AS node FROM edges
    UNION
    SELECT TO_NODE AS node FROM edges
),
-- 递归遍历连通分量，记录每个节点的根节点（分量标识）及已访问节点
connected_components AS (
    SELECT
        node,
        node AS root_node,
        ARRAY_CONSTRUCT(node) AS visited_nodes
    FROM nodes
    UNION ALL
    SELECT
        n.node,
        cc.root_node,
        ARRAY_APPEND(cc.visited_nodes, n.node)
    FROM connected_components cc
    -- 正向遍历边
    JOIN edges e ON cc.node = e.FROM_NODE
    JOIN nodes n ON e.TO_NODE = n.node
    WHERE NOT ARRAY_CONTAINS(cc.visited_nodes, n.node)
    UNION ALL
    SELECT
        n.node,
        cc.root_node,
        ARRAY_APPEND(cc.visited_nodes, n.node)
    FROM connected_components cc
    -- 反向遍历边，确保无向连通
    JOIN edges e ON cc.node = e.TO_NODE
    JOIN nodes n ON e.FROM_NODE = n.node
    WHERE NOT ARRAY_CONTAINS(cc.visited_nodes, n.node)
),
-- 去重，每个节点仅保留一个根节点
unique_components AS (
    SELECT DISTINCT node, root_node FROM connected_components
),
-- 为每个根节点分配自增的分组ID
group_mapping AS (
    SELECT
        root_node,
        DENSE_RANK() OVER (ORDER BY root_node) AS GROUP_NAME
    FROM unique_components
)
-- 关联边数据与分组信息
SELECT
    e.FROM_NODE,
    e.TO_NODE,
    gm.GROUP_NAME
FROM edges e
JOIN unique_components uc1 ON e.FROM_NODE = uc1.node
JOIN group_mapping gm ON uc1.root_node = gm.root_node
ORDER BY GROUP_NAME, FROM_NODE, TO_NODE;

方案说明 #

1. 节点集合：先提取所有唯一节点，确保遍历覆盖所有连通分支。
2. 递归遍历：通过visited_nodes数组跟踪已访问节点，避免环导致的无限递归；同时正向+反向遍历边，确保无向连通的节点被归为同一分量。
3. 分组映射：以连通分量的根节点为标识，用DENSE_RANK()生成连续的分组ID。
4. 关联输出：将边数据与分组映射关联，得到每条边的分组标识。

内容的提问来源于stack exchange，提问作者Jay