Wie finde ich mit SQL alle verbundenen Untergraphen in einem ungerichteten Diagramm?

So finden Sie alle verbundenen Untergraphen eines ungerichteten Graphen

Problemdefinition:
Gegeben sei ein ungerichteter Graph dargestellt durch eine Tabelle mit zwei Spalten, Bezeichner1 und Bezeichner2, wobei jede Zeile eine Kante zwischen den beiden Bezeichnern darstellt. Die Aufgabe besteht darin, alle verbundenen Untergraphen im Diagramm zu finden. Ein verbundener Untergraph ist eine Menge von Bezeichnern, die direkt oder indirekt durch andere Bezeichner verknüpft sind. Die Ausgabe sollte die Bezeichner in jedem Untergraphen enthalten und jedem Untergraphen eine eindeutige Gruppen-ID zuweisen.

Abfrage zum Suchen verbundener Untergraphen:

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

Erklärung :

• CTE_Idents: Dieser Common Table Expression (CTE) identifiziert alle unterschiedlichen eindeutigen Bezeichner sowohl im Identifier1 als auch im Identifier2 Spalten.
• CTE_Pairs: Es extrahiert und kombiniert Kanten aus der EdgeTable, um alle eindeutigen Bezeichnerpaare darzustellen.
• CTE_Recursive: Dieser rekursive CTE durchläuft den Graphen beginnend mit jedem eindeutigen Bezeichner und erstellt einen durch Kommas getrennten Pfad verbundener Bezeichner. Es stoppt, wenn eine Schleife erkannt wird.
• CTE_CleanResult: Es behält nur relevante Informationen von CTE_Recursive bei und stellt eine eindeutige Liste von Bezeichnern bereit, die mit jedem AnchorIdent.

• Final SELECT:

  Es kombiniert die Ergebnisse, um die Bezeichner und ihre verbundenen Komponenten zu generieren.
  • Null Werte in
  • GroupMembers werden durch den Bezeichner ersetzt.
  Jeder verbundenen Komponente wird mit DENSE_RANK() eine eindeutige
  • GroupID zugewiesen.

Das obige ist der detaillierte Inhalt vonWie finde ich mit SQL alle verbundenen Untergraphen in einem ungerichteten Diagramm?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!