How to Find All Connected Subgraphs in an Undirected Graph Using a Recursive CTE?

How to Find All Connected Subgraphs of an Undirected Graph

Problem:

Given a table with two columns containing identifiers, find all groups of identifiers that are connected to each other.

Example Table:

ID	Identifier1	Identifier2
1	a	c
2	b	f
3	a	g
4	c	h
5	b	j
6	d	f
7	e	k
8	i
9	l	h

Desired Output:

Identifier	Gr_ID	Gr.Members
a	1	(a,c,g,h,l)
b	2	(b,d,f,j)
c	1	(a,c,g,h,l)
d	2	(b,d,f,j)
e	3	(e,k)
f	2	(b,d,f,j)
g	1	(a,c,g,h,l)
h	1	(a,c,g,h,l)
j	2	(b,d,f,j)
k	3	(e,k)
l	1	(a,c,g,h,l)
i	4	(i)

Solution:

The following query uses a single recursive query to find all connected subgraphs:

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

Sample Output:

Identifier	Gr_ID	Gr.Members
a	1	(a,c,g,h,l)
b	2	(b,d,f,j)
c	1	(a,c,g,h,l)
d	2	(b,d,f,j)
e	3	(e,k)
f	2	(b,d,f,j)
g	1	(a,c,g,h,l)
h	1	(a,c,g,h,l)
i	4	(i)
j	2	(b,d,f,j)
k	3	(e,k)
l	1	(a,c,g,h,l)
z	5	(z)

Explanation:

• The query uses a recursive CTE to find all paths in the graph that follow the edges defined in the CTE_Pairs table.
• The CTE_Idents table contains all the unique identifiers in the graph.
• The CTE_CleanResult table extracts the connected identifiers for each anchor identifier.
• The final SELECT statement uses a combination of FOR XML PATH and CROSS APPLY to concatenate the connected identifiers for each group.
• DENSE_RANK() is used to assign unique Group IDs to each group.

The above is the detailed content of How to Find All Connected Subgraphs in an Undirected Graph Using a Recursive CTE?. For more information, please follow other related articles on the PHP Chinese website!