如何使用 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_Idents：此通用表表达式 (CTE) 标识 Identifier1 和 Identifier2 列。
• CTE_Pairs：它从 EdgeTable 中提取并组合边来表示所有唯一的标识符对。
• CTE_Recursive：此递归 CTE 从每个唯一标识符开始遍历图表，构建连接标识符的逗号分隔路径。当检测到循环时它会停止。
• CTE_CleanResult：它仅保留来自 CTE_Recursive 的相关信息，提供连接到每个 AnchorIdent.
• 最终 SELECT

  :

  它组合结果以生成标识符及其连接组件。
  • Null
  GroupMembers
  • 中的值将替换为标识符。使用 DENSE_RANK() 将唯一的
  GroupID
  • 分配给每个连接的组件。

以上是如何使用 SQL 查找无向图中的所有连通子图？的详细内容。更多信息请关注PHP中文网其他相关文章！