sql-server - SQL递归CTE图遍历

Question

我有一个包含一小组相关节点的表。我希望能够识别所有相关的节点。

-- Example of some small related nodes.
--         (14)   (5) (8)    (10) (3)
--         /        \   \      \  /
--  (11)-(2)       (12)-(9)    (7)
--         \        /          /  \
--         (4)    (6)        (1)  (13) 

DECLARE @Graph TABLE  (
    A SmallInt NOT NULL,
    B SmallInt NOT NULL
)

INSERT INTO @Graph (A, B)
VALUES 
    (11,  2), ( 2, 14), ( 2,  4), ( 5, 12),
    ( 6, 12), ( 12, 9), ( 8,  9), (10,  7),
    ( 1,  7), ( 7, 13), ( 7,  3);

想要的结果

1, 13

2、14

3、13

4、14

5、12

6、12

7、13

8、12

9、12

10、13

11、14

12、12

13、13

14、14

CTE 接近正确答案，但不完全正确。

WITH Src AS (
    SELECT A, B FROM @Graph
)
, Recurse (A, B) AS (
    SELECT A, B FROM Src
    UNION ALL
    SELECT S.A, R.B FROM Src S INNER JOIN Recurse R ON S.B = R.A 
)
, List AS (
    SELECT A, B FROM Recurse 
    UNION SELECT A, A FROM Src
    UNION SELECT B, B FROM Src
)
SELECT A, MAX(B) B FROM List GROUP BY A ORDER BY 1, 2;

查询结果

1, 13

2、14

3、3 <- 错误结果

4、4 <- 错误结果

5、12

6、12

7、13

8、9 <- 错误结果

9、9 <- 错误结果

10、13

11、14

12、12

13、13

14、14

我决定使用 MAX 节点号将节点关联在一起，但其他一些方法也是可以接受的。

Answer 1

EzLo 必须将我引向另一篇文章 (How to find all connected subgraphs of an undirected graph) 从而使我能够撰写正确答案，因此必须获得赞誉。

DECLARE @Graph TABLE  (
    A SmallInt NOT NULL,
    B SmallInt NOT NULL
)

INSERT INTO @Graph (A, B)
VALUES 
    (11,  2), ( 2, 14), ( 2,  4), ( 5, 12),
    ( 6, 12), ( 12, 9), ( 8,  9), (10,  7),
    ( 1,  7), ( 7, 13), ( 7,  3);


WITH CTE_Idents AS (
    SELECT A AS Ident FROM @Graph
    UNION SELECT B AS Ident FROM @Graph
)
, CTE_Pairs AS (
    SELECT A AS Ident1, B AS Ident2 FROM @Graph WHERE A <> B
    UNION SELECT B AS Ident1, A AS Ident2 FROM @Graph WHERE A <> B
)
, CTE_Recursive AS (
    SELECT
        CTE_Idents.Ident AS AnchorIdent,
        Ident1,
        Ident2,
        CAST(',' + CAST(Ident1 AS VARCHAR(2)) + ',' + CAST(Ident2 AS VARCHAR(2)) + ',' AS varchar(8000)) AS IdentPath
    FROM 
            CTE_Pairs
        INNER JOIN 
            CTE_Idents 
                ON CTE_Idents.Ident = CTE_Pairs.Ident1

    UNION ALL

    SELECT 
        CTE_Recursive.AnchorIdent, 
        CTE_Pairs.Ident1, 
        CTE_Pairs.Ident2, 
        CAST(CTE_Recursive.IdentPath + CAST(CTE_Pairs.Ident2 AS VARCHAR(2)) + ',' AS varchar(8000)) AS IdentPath
    FROM
            CTE_Pairs
        INNER JOIN 
            CTE_Recursive 
                ON CTE_Recursive.Ident2 = CTE_Pairs.Ident1
    WHERE
        CTE_Recursive.IdentPath NOT LIKE CAST('%,' + CAST(CTE_Pairs.Ident2 AS VARCHAR(2)) + ',%' AS varchar(8000))
)
, CTE_RecursionResult AS (
    SELECT AnchorIdent, Ident1, Ident2 FROM CTE_Recursive
)
, CTE_CleanResult AS (
    SELECT AnchorIdent, Ident1 AS Ident FROM CTE_RecursionResult
    UNION SELECT AnchorIdent, Ident2 AS Ident FROM CTE_RecursionResult
)
SELECT AnchorIdent, MAX(Ident) AS Ident FROM CTE_CleanResult GROUP BY AnchorIdent ORDER BY AnchorIdent