我们如何在由两列'Identifier1”和'Identifier2”表示的无向图中对相关标识符进行分组，并为它们分配唯一的组ID？

在无向图中查找连通子图

问题：

给定一个由两列“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中文网其他相关文章！