Обход 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 <- неправильный результат </strong>
• 4, 4 <- неправильный результат </strong>
• 5, 12
• 6, 12
• 7, 13
• 8, 9 <- Неверный результат </strong>
• 9, 9 <- Неверный результат </strong>
• 10, 13
• 11, 14
• 12, 12
• 13, 13
• 14, 14

Я решил использовать номер узла MAX, чтобы связать узлы вместе, но какой-то другой метод был бы приемлем.

Answer 1

EzLo должен получить кредит за то, что привел меня к другому сообщению ( Как найти все связанные подграфы неориентированного графа ), которые позволили мне составить правильный ответ.

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