Rumah > Artikel > pangkalan data > Bagaimana Mencari Semua Subgraf Bersambung dalam Graf Tidak Berarah Menggunakan CTE Rekursif?
Cara Mencari Semua Subgraf Bersambung bagi Graf Tidak Berarah
Masalah:
Diberikan jadual dengan dua lajur yang mengandungi pengecam, cari semua kumpulan pengecam yang disambungkan antara satu sama lain.
Contoh Jadual:
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 |
Output yang Diingini:
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) |
Penyelesaian:
Pertanyaan berikut menggunakan pertanyaan rekursif tunggal untuk mencari semua subgraf yang disambungkan:
<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>
Sampel 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) |
Penjelasan:
Atas ialah kandungan terperinci Bagaimana Mencari Semua Subgraf Bersambung dalam Graf Tidak Berarah Menggunakan CTE Rekursif?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!