search
HomeDatabaseMysql TutorialHow to Find All Connected Subgraphs in an Undirected Graph Using a Recursive CTE?

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!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
How do you alter a table in MySQL using the ALTER TABLE statement?How do you alter a table in MySQL using the ALTER TABLE statement?Mar 19, 2025 pm 03:51 PM

The article discusses using MySQL's ALTER TABLE statement to modify tables, including adding/dropping columns, renaming tables/columns, and changing column data types.

How do I configure SSL/TLS encryption for MySQL connections?How do I configure SSL/TLS encryption for MySQL connections?Mar 18, 2025 pm 12:01 PM

Article discusses configuring SSL/TLS encryption for MySQL, including certificate generation and verification. Main issue is using self-signed certificates' security implications.[Character count: 159]

How do you handle large datasets in MySQL?How do you handle large datasets in MySQL?Mar 21, 2025 pm 12:15 PM

Article discusses strategies for handling large datasets in MySQL, including partitioning, sharding, indexing, and query optimization.

What are some popular MySQL GUI tools (e.g., MySQL Workbench, phpMyAdmin)?What are some popular MySQL GUI tools (e.g., MySQL Workbench, phpMyAdmin)?Mar 21, 2025 pm 06:28 PM

Article discusses popular MySQL GUI tools like MySQL Workbench and phpMyAdmin, comparing their features and suitability for beginners and advanced users.[159 characters]

How do you drop a table in MySQL using the DROP TABLE statement?How do you drop a table in MySQL using the DROP TABLE statement?Mar 19, 2025 pm 03:52 PM

The article discusses dropping tables in MySQL using the DROP TABLE statement, emphasizing precautions and risks. It highlights that the action is irreversible without backups, detailing recovery methods and potential production environment hazards.

How do you create indexes on JSON columns?How do you create indexes on JSON columns?Mar 21, 2025 pm 12:13 PM

The article discusses creating indexes on JSON columns in various databases like PostgreSQL, MySQL, and MongoDB to enhance query performance. It explains the syntax and benefits of indexing specific JSON paths, and lists supported database systems.

How do you represent relationships using foreign keys?How do you represent relationships using foreign keys?Mar 19, 2025 pm 03:48 PM

Article discusses using foreign keys to represent relationships in databases, focusing on best practices, data integrity, and common pitfalls to avoid.

How do I secure MySQL against common vulnerabilities (SQL injection, brute-force attacks)?How do I secure MySQL against common vulnerabilities (SQL injection, brute-force attacks)?Mar 18, 2025 pm 12:00 PM

Article discusses securing MySQL against SQL injection and brute-force attacks using prepared statements, input validation, and strong password policies.(159 characters)

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools