Comment rechercher tous les sous-graphes connectés dans un graphique non orienté à l'aide de SQL ?

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

Définition du problème :
Étant donné un graphe non orienté représenté par un tableau à deux colonnes, Identifier1 et Identifier2, où chaque ligne représente une arête entre les deux identifiants, la tâche est de trouver tous les sous-graphes connectés dans le graphique. Un sous-graphe connecté est un ensemble d'identifiants liés directement ou indirectement par d'autres identifiants. Le résultat doit inclure les identifiants dans chaque sous-graphe et attribuer un ID de groupe unique à chaque sous-graphe.

Requête pour trouver les sous-graphes connectés :

<code class="sql">WITH
CTE_Idents
AS
(
    SELECT DISTINCT
        CASE WHEN Ident1 IS NOT NULL THEN Ident1 ELSE Ident2 END AS Ident
    FROM EdgeTable
),
CTE_Pairs
AS
(
    SELECT Ident1, Ident2
    FROM EdgeTable
),
CTE_Recursive
AS
(
    SELECT
        CAST(AnchorIdent AS VARCHAR(8000)) AS AnchorIdent,
        Ident1,
        Ident2,
        CAST(',' + Ident1 + ',' + Ident2 + ',' AS VARCHAR(8000)) AS IdentPath,
        1 AS Level
    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.Level + 1
    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))
)
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>

Explication :

• CTE_Idents : Cette expression de table commune (CTE) identifie tous les identifiants uniques distincts dans les Identifier1 et Identifier2 colonnes.
• CTE_Pairs : il extrait et combine les arêtes du EdgeTable pour représenter toutes les paires uniques d'identifiants.
• CTE_Recursive : Ce CTE récursif parcourt le graphique à partir de chaque identifiant unique, en construisant un chemin d'identifiants connectés séparés par des virgules. Il s'arrête lorsqu'une boucle est détectée.
• CTE_CleanResult : Il conserve uniquement les informations pertinentes de CTE_Recursive, fournissant une liste distincte d'identifiants connectés à chaque AnchorIdent.

• SÉLECTION Finale :

  • Il combine les résultats pour générer les identifiants et leurs composants connectés.
  • Null les valeurs dans GroupMembers sont remplacées par l'identifiant.
  • Un GroupID unique est attribué à chaque composant connecté à l'aide de DENSE_RANK().

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!