Comment trouver tous les sous-graphes connectés dans un graphique non orienté à l'aide d'un CTE récursif ?

Comment trouver tous les sous-graphes connectés d'un graphe non orienté

Problème :

Étant donné un tableau avec deux colonnes contenant des identifiants, recherchez tous les groupes d'identifiants connectés les uns aux autres.

Exemple de tableau :

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

Sortie souhaitée :

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 :

La requête suivante utilise une seule requête récursive pour trouver tous les sous-graphes connectés :

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

Exemple de sortie :

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)

Explication :

• La requête utilise un CTE récursif pour trouver tous les chemins dans le graphique qui suivent les arêtes définies dans la table CTE_Pairs.
• Le La table CTE_Idents contient tous les identifiants uniques du graphique.
• La table CTE_CleanResult extrait les identifiants connectés pour chaque identifiant d'ancre.
• L'instruction SELECT finale utilise une combinaison de FOR XML PATH et CROSS APPLY pour concaténer les identifiants connectés pour chaque groupe.
• DENSE_RANK() est utilisé pour attribuer des identifiants de groupe uniques à chaque groupe.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!