如何使用遞歸 CTE 找出無向圖中的所有連通子圖？

如何找出無向圖的所有連通子圖

問題：

問題：

給定一個有兩列包含標識符的表，找到彼此連接的所有標識符組。

ID	Identifier1	Identifier2
1	a	c
2	b	f
3	a	g
4	c	h
5	b	j
6	d	f
7	e	k
8	i
9	l	h

範例表：

Identifier	Gr_ID	Gr.Members
a	1	(a,c,g,h,l)
b	2	(b,d,f,j)
c	1	(a,c,g,h,l)
d	2	(b,d,f,j)
e	3	(e,k)
f	2	(b,d,f,j)
g	1	(a,c,g,h,l)
h	1	(a,c,g,h,l)
j	2	(b,d,f,j)
k	3	(e,k)
l	1	(a,c,g,h,l)
i	4	(i)

所需輸出：

解決方案：

<code class="sql">WITH
CTE_Idents
AS
(
    SELECT Ident1 AS Ident
    FROM @T

    UNION

    SELECT Ident2 AS Ident
    FROM @T
)
,CTE_Pairs
AS
(
    SELECT Ident1, Ident2
    FROM @T
    WHERE Ident1 <> Ident2

    UNION

    SELECT Ident2 AS Ident1, Ident1 AS Ident2
    FROM @T
    WHERE Ident1 <> Ident2
)
,CTE_Recursive
AS
(
    SELECT
        CAST(CTE_Idents.Ident AS varchar(8000)) AS AnchorIdent 
        , Ident1
        , Ident2
        , CAST(',' + Ident1 + ',' + Ident2 + ',' AS varchar(8000)) AS IdentPath
        , 1 AS Lvl
    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 + CTE_Pairs.Ident2 + ',' AS varchar(8000)) AS IdentPath
        , CTE_Recursive.Lvl + 1 AS Lvl
    FROM
        CTE_Pairs
        INNER JOIN CTE_Recursive ON CTE_Recursive.Ident2 = CTE_Pairs.Ident1
    WHERE
        CTE_Recursive.IdentPath NOT LIKE CAST('%,' + CTE_Pairs.Ident2 + ',%' 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
    CTE_Idents.Ident
    ,CASE WHEN CA_Data.XML_Value IS NULL 
    THEN CTE_Idents.Ident ELSE CA_Data.XML_Value END AS GroupMembers
    ,DENSE_RANK() OVER(ORDER BY 
        CASE WHEN CA_Data.XML_Value IS NULL 
        THEN CTE_Idents.Ident ELSE CA_Data.XML_Value END
    ) AS GroupID
FROM
    CTE_Idents
    CROSS APPLY
    (
        SELECT CTE_CleanResult.Ident+','
        FROM CTE_CleanResult
        WHERE CTE_CleanResult.AnchorIdent = CTE_Idents.Ident
        ORDER BY CTE_CleanResult.Ident FOR XML PATH(''), TYPE
    ) AS CA_XML(XML_Value)
    CROSS APPLY
    (
        SELECT CA_XML.XML_Value.value('.', 'NVARCHAR(MAX)')
    ) AS CA_Data(XML_Value)
WHERE
    CTE_Idents.Ident IS NOT NULL
ORDER BY Ident;</code>

以下查詢使用單一遞迴查詢來找出所有連接的子圖：

Identifier	Gr_ID	Gr.Members
a	1	(a,c,g,h,l)
b	2	(b,d,f,j)
c	1	(a,c,g,h,l)
d	2	(b,d,f,j)
e	3	(e,k)
f	2	(b,d,f,j)
g	1	(a,c,g,h,l)
h	1	(a,c,g,h,l)
i	4	(i)
j	2	(b,d,f,j)
k	3	(e,k)
l	1	(a,c,g,h,l)
z	5	(z)

範例輸出：範例輸出：

說明：

• 查詢使用遞迴 CTE 來找出圖中沿著 CTE_Pairs 表中定義的邊的所有路徑。
• CTE_Idents 表包含圖中的所有唯一識別碼。
• CTE_CleanResult 資料表擷取每個錨點標識符的連線標識符。
• 最終的 SELECT 語句使用 FOR XML PATH 和 CROSS APPLY 的組合來連接每組的連接識別碼。
• DENSE_RANK() 用於為每個群組分配唯一的群組 ID。

以上是如何使用遞歸 CTE 找出無向圖中的所有連通子圖？的詳細內容。更多資訊請關注PHP中文網其他相關文章！