無向グラフ内の接続されたサブグラフの検索

問題:

2 つの列 'Identifier1' と 'Identifier2' で表される無向グラフがあるとします。相互に関連する識別子をグループ化し、一意のグループ ID を割り当てるにはどうすればよいですか?

解決策:

この問題は、データをグラフ内のエッジとして扱い、すべてのエッジを走査することで解決できます。再帰的に。

再帰アルゴリズム:

1. 両方の列の一意の識別子をすべて含むテーブルを作成します。
2. 両方の列のすべてのエッジ (識別子のペア) を含むテーブルを作成します。方向。
3. 各識別子から開始してグラフを走査し、走査された識別子のパスを構築する再帰クエリを定義します。
4. 開始識別子 (アンカー識別子) によって結果をグループ化し、接続されたコンポーネントを識別します。
5. アンカー識別子に基づいて各接続コンポーネントに一意のグループ ID を割り当てます。

クエリの例 (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;

キー ポイント:

• 再帰 CTE (共通テーブル式) はグラフを走査し、接続されたコンポーネントを構築します。
• 最後の SELECT ステートメントはグループを割り当てます。 ID を取得し、必要な形式で出力を生成します。
• このソリューションは、冗長な計算を回避し、効率的な結果を提供するように最適化されています。