Bagaimana untuk Mencari Semua Subgraf Bersambung dalam Graf Tidak Berarah Menggunakan SQL?

Cara mencari semua subgraf bersambung bagi graf tidak berarah

Definisi Masalah:
Diberi graf tidak berarah diwakili oleh jadual dengan dua lajur, Pengecam1 dan Pengecam2, di mana setiap baris mewakili tepi antara dua pengecam, tugasnya adalah untuk mencari semua subgraf yang disambungkan dalam graf. Subgraf bersambung ialah set pengecam yang dipautkan secara langsung atau tidak langsung oleh pengecam lain. Output hendaklah termasuk pengecam dalam setiap subgraf dan memberikan ID kumpulan unik kepada setiap subgraf.

Pertanyaan untuk Mencari Subgraf Bersambung:

<code class="sql">WITH
CTE_Idents
AS
(
    SELECT DISTINCT
        CASE WHEN Ident1 IS NOT NULL THEN Ident1 ELSE Ident2 END AS Ident
    FROM EdgeTable
),
CTE_Pairs
AS
(
    SELECT Ident1, Ident2
    FROM EdgeTable
),
CTE_Recursive
AS
(
    SELECT
        CAST(AnchorIdent AS VARCHAR(8000)) AS AnchorIdent,
        Ident1,
        Ident2,
        CAST(',' + Ident1 + ',' + Ident2 + ',' AS VARCHAR(8000)) AS IdentPath,
        1 AS Level
    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.Level + 1
    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))
)
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>

Penjelasan :

• CTE_Idents: Ungkapan Jadual Biasa (CTE) ini mengenal pasti semua pengecam unik yang berbeza dalam kedua-dua Identifier1 dan Identifier2 lajur.
• CTE_Pairs: Ia mengekstrak dan menggabungkan tepi daripada EdgeTable untuk mewakili semua pasangan unik pengecam.
• CTE_Recursive: CTE rekursif ini merentasi graf bermula dari setiap pengecam unik, membina laluan yang dipisahkan koma bagi pengecam bersambung. Ia berhenti apabila gelung dikesan.
• CTE_CleanResult: Ia mengekalkan hanya maklumat yang berkaitan daripada CTE_Recursive, menyediakan senarai pengecam yang berbeza yang disambungkan kepada setiap AnchorIdent.

• PILIHAN Akhir:

  • Ia menggabungkan hasil untuk menjana pengecam dan komponennya yang disambungkan.
  • Null nilai dalam GroupMembers digantikan dengan pengecam.
  • Unik GroupID diberikan kepada setiap komponen yang disambungkan menggunakan DENSE_RANK().

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