Bagaimana Mencari Semua Subgraf Bersambung dalam Graf Tidak Berarah Menggunakan CTE Rekursif?

Cara Mencari Semua Subgraf Bersambung bagi Graf Tidak Berarah

Masalah:

Diberikan jadual dengan dua lajur yang mengandungi pengecam, cari semua kumpulan pengecam yang disambungkan antara satu sama lain.

Contoh Jadual:

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

Output yang Diingini:

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)

Penyelesaian:

Pertanyaan berikut menggunakan pertanyaan rekursif tunggal untuk mencari semua subgraf yang disambungkan:

<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>

Sampel Output:

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)

Penjelasan:

• Pertanyaan menggunakan CTE rekursif untuk mencari semua laluan dalam graf yang mengikuti tepi yang ditakrifkan dalam jadual CTE_Pairs.
• The Jadual CTE_Idents mengandungi semua pengecam unik dalam graf.
• Jadual CTE_CleanResult mengekstrak pengecam yang disambungkan untuk setiap pengecam utama.
• Pernyataan SELECT akhir menggunakan gabungan FOR XML PATH dan CROSS APPLY untuk gabungkan pengecam yang disambungkan untuk setiap kumpulan.
• DENSE_RANK() digunakan untuk memberikan ID Kumpulan unik kepada setiap kumpulan.

Atas ialah kandungan terperinci Bagaimana Mencari Semua Subgraf Bersambung dalam Graf Tidak Berarah Menggunakan CTE Rekursif?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!