\'Identifier1\' 및 \'Identifier2\'라는 두 개의 열로 표시되는 무방향 그래프에서 관련 식별자를 어떻게 그룹화하고 고유한 그룹 ID를 할당합니까?

무방향 그래프에서 연결된 하위 그래프 찾기

문제:

'식별자1'과 '식별자2'라는 두 개의 열로 표현되는 무방향 그래프가 주어지면, 서로 관련된 식별자를 어떻게 그룹화하고 고유한 그룹 ID를 할당합니까?

해결책:

이 문제는 데이터를 그래프의 모서리로 처리하고 모든 모서리를 탐색하여 해결할 수 있습니다.

재귀 알고리즘:

1. 두 열의 모든 고유 식별자를 포함하는 테이블을 생성합니다.
2. 두 열의 모든 가장자리(식별자 쌍)를 포함하는 테이블을 생성합니다. 방향.
3. 각 식별자에서 시작하여 그래프를 순회하고 순회된 식별자의 경로를 구축하는 재귀 쿼리를 정의합니다.
4. 결과를 시작 식별자(앵커 식별자)별로 그룹화하여 연결된 구성 요소를 식별합니다.
5. 앵커 식별자를 기반으로 연결된 각 구성 요소에 고유한 그룹 ID를 할당합니다.

예시 쿼리(SQL):

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

핵심 사항:

• 재귀적 CTE(공통 테이블 표현식)는 그래프를 순회하며 연결된 구성요소를 구축합니다.
• 마지막 SELECT 문은 그룹 ID를 할당하고 원하는 형식으로 출력을 생성합니다.
• 중복 계산을 방지하고 효율적인 결과를 제공하도록 최적화된 솔루션입니다.

위 내용은 \'Identifier1\' 및 \'Identifier2\'라는 두 개의 열로 표시되는 무방향 그래프에서 관련 식별자를 어떻게 그룹화하고 고유한 그룹 ID를 할당합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!