


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!

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

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]

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

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

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.

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.

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

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


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function

ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment

VSCode Windows 64-bit Download
A free and powerful IDE editor launched by Microsoft

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Dreamweaver Mac version
Visual web development tools