Bagaimanakah kita mengumpulkan pengecam berkaitan dalam graf tidak terarah yang diwakili oleh dua lajur, \'Pengenal1\' dan \'Pengecam2\', dan memberikan ID kumpulan unik kepada mereka?

Mencari Subgraf Bersambung dalam Graf Tidak Berhala

Masalah:

Memandangkan graf tidak berarah yang diwakili oleh dua lajur, 'Pengenal1' dan 'Pengenal2', bagaimanakah kita mengumpulkan pengecam yang berkaitan antara satu sama lain dan memberikan mereka ID kumpulan unik?

Penyelesaian:

Masalah ini boleh diselesaikan dengan menganggap data sebagai tepi dalam graf dan merentasi semua tepi secara rekursif.

Algoritma Rekursif:

1. Buat jadual yang mengandungi semua pengecam unik daripada kedua-dua lajur.
2. Buat jadual yang mengandungi semua tepi (pasangan pengecam) dalam kedua-dua lajur. arah.
3. Tentukan pertanyaan rekursif yang merentasi graf bermula dari setiap pengecam dan membina laluan pengecam yang dilalui.
4. Kumpulkan hasil mengikut pengecam permulaan (pengecam sauh) untuk mengenal pasti komponen yang disambungkan.
5. Tetapkan ID kumpulan unik kepada setiap komponen yang disambungkan berdasarkan pengecam utama.

Contoh Pertanyaan (SQL):

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

Inti Utama:

• CTE rekursif (Ungkapan Jadual Biasa) merentasi graf dan membina komponen yang disambungkan.
• Pernyataan SELECT akhir memberikan ID kumpulan dan menjana output dalam format yang diingini.
• Penyelesaian ini dioptimumkan untuk mengelakkan pengiraan berlebihan dan memberikan hasil yang cekap.

Atas ialah kandungan terperinci Bagaimanakah kita mengumpulkan pengecam berkaitan dalam graf tidak terarah yang diwakili oleh dua lajur, \'Pengenal1\' dan \'Pengecam2\', dan memberikan ID kumpulan unik kepada mereka?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!