如何找出無向圖的所有連通子圖
問題:
問題:給定一個有兩列包含標識符的表,找到彼此連接的所有標識符組。
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 |
範例表:
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) |
所需輸出:
解決方案:<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>
以下查詢使用單一遞迴查詢來找出所有連接的子圖:
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) |
說明:
以上是如何使用遞歸 CTE 找出無向圖中的所有連通子圖?的詳細內容。更多資訊請關注PHP中文網其他相關文章!