如何使用 SQL 尋找無向圖中的所有連通子圖？

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

問題定義：
給定一個無向向圖由具有兩列的表表示，Identifier1 和Identifier2，其中每一行代表兩個標識符之間的一條邊，任務是找到圖中所有連通的子圖。連接子圖是由其他識別碼直接或間接連結的一組識別碼。輸出應包含每個子圖中的標識符，並為每個子圖分配唯一的群組 ID。

找出連接子圖的查詢：

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

說明:

• 說明:
：此通用表格表達式(CTE) 識別
• Identifier1 和Identifier2 欄位。
CTE_Pairs
• ：它從 EdgeTable 中提取並組合邊來表示所有唯一的識別碼對。
• CTE_Recursive：此遞歸 CTE 從每個唯一識別碼開始遍歷圖表，建立連接識別碼的逗號分隔路徑。當檢測到循環時它會停止。 CTE_CleanResult：它僅保留來自
CTE_Recursive
• 的相關信息，提供連接到每個

  AnchorIdent

  最終SELECT
  :
  • 它組合結果以產生標識符及其連接組件。 Null
  GroupMembers
  • 中的值將會被取代為識別碼。 使用 DENSE_RANK() 將唯一的
  GroupID
  指派給每個連接的元件。

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