SQL을 사용하여 무방향 그래프에서 연결된 모든 하위 그래프를 찾는 방법은 무엇입니까?

무방향 그래프의 연결된 모든 하위 그래프를 찾는 방법

문제 정의:
무방향 그래프가 제공됩니다. Identifier1 및 Identifier2라는 두 개의 열이 있는 테이블로 표현됩니다. 여기서 각 행은 두 식별자 사이의 가장자리를 나타냅니다. 작업은 그래프에서 연결된 모든 하위 그래프를 찾는 것입니다. 연결된 하위 그래프는 다른 식별자에 의해 직접 또는 간접적으로 연결된 식별자 집합입니다. 출력에는 각 하위 그래프의 식별자가 포함되어야 하며 각 하위 그래프에 고유한 그룹 ID를 할당해야 합니다.

연결된 하위 그래프를 찾기 위한 쿼리:

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

설명 :

• CTE_Idents: 이 CTE(공통 테이블 표현식)는 Identifier1 및 Identifier2 columns.
• CTE_Pairs: EdgeTable에서 가장자리를 추출하고 결합하여 모든 고유한 식별자 쌍을 나타냅니다.
• CTE_Recursive: 이 재귀 CTE는 각 고유 식별자부터 시작하여 그래프를 순회하여 연결된 식별자의 쉼표로 구분된 경로를 구축합니다. 루프가 감지되면 중지됩니다.
• CTE_CleanResult: CTE_Recursive에서 관련 정보만 유지하여 각 AnchorIdent.
• 최종 SELECT

  :

  결과를 결합하여 식별자와 연결된 구성 요소를 생성합니다.
  • Null
  GroupMembers
  • 의 값은 식별자로 대체됩니다.DENSE_RANK()를 사용하여 연결된 각 구성 요소에 고유한
  GroupID
  • 가 할당됩니다.

위 내용은 SQL을 사용하여 무방향 그래프에서 연결된 모든 하위 그래프를 찾는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!