首頁 > 資料庫 > mysql教程 > 我們如何在由兩列「Identifier1」和「Identifier2」所表示的無向圖中將相關識別碼分組,並為它們指派唯一的群組ID?

我們如何在由兩列「Identifier1」和「Identifier2」所表示的無向圖中將相關識別碼分組,並為它們指派唯一的群組ID?

Mary-Kate Olsen
發布: 2024-10-29 06:32:31
原創
794 人瀏覽過

How do we group related identifiers in an undirected graph represented by two columns, 'Identifier1' and 'Identifier2', and assign them unique group IDs?

在無向圖中找出連通子圖

問題:

給定一個由兩列「Identifier1」和「Identifier2」表示的無向圖,我們如何將彼此相關的識別碼進行分組並為它們分配唯一的群組ID?

解決方案:

可以透過將資料視為圖中的邊並遍歷所有邊來解決此問題遞歸地。

遞歸演算法:

  1. 建立一個包含兩個欄位中所有唯一識別碼的表。
  2. 建立一個包含兩列中所有邊(標識符對)的表。方向。
  3. 定義一個遞歸查詢,從每個標識符開始遍歷圖形,並建立遍歷標識符的路徑。
  4. 以起始標識符(錨點標識符)將結果分組,以識別連接的組件。
  5. 根據錨定標識符為每個連接的組件分配唯一的群組 ID。

範例查詢(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>
登入後複製

重點:

  • 遞歸CTE(公用表表達式)遍歷圖形並建立連接的元件。
  • 最終的 SELECT 語句分配組 ID 並以所需格式產生輸出。
  • 此解決方案經過最佳化,可以避免冗餘計算並提供高效的結果。

以上是我們如何在由兩列「Identifier1」和「Identifier2」所表示的無向圖中將相關識別碼分組,並為它們指派唯一的群組ID?的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板