> 데이터 베이스 > MySQL 튜토리얼 > SQL을 사용하여 무방향 그래프에서 연결된 모든 하위 그래프를 찾는 방법은 무엇입니까?

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

Mary-Kate Olsen
풀어 주다: 2024-10-29 12:52:02
원래의
935명이 탐색했습니다.

How to Find All Connected Subgraphs in an Undirected Graph Using SQL?

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

문제 정의:
무방향 그래프가 제공됩니다. Identifier1Identifier2라는 두 개의 열이 있는 테이블로 표현됩니다. 여기서 각 행은 두 식별자 사이의 가장자리를 나타냅니다. 작업은 그래프에서 연결된 모든 하위 그래프를 찾는 것입니다. 연결된 하위 그래프는 다른 식별자에 의해 직접 또는 간접적으로 연결된 식별자 집합입니다. 출력에는 각 하위 그래프의 식별자가 포함되어야 하며 각 하위 그래프에 고유한 그룹 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(공통 테이블 표현식)는 Identifier1Identifier2 columns.
  • CTE_Pairs: EdgeTable에서 가장자리를 추출하고 결합하여 모든 고유한 식별자 쌍을 나타냅니다.
  • CTE_Recursive: 이 재귀 CTE는 각 고유 식별자부터 시작하여 그래프를 순회하여 연결된 식별자의 쉼표로 구분된 경로를 구축합니다. 루프가 감지되면 중지됩니다.
  • CTE_CleanResult: CTE_Recursive에서 관련 정보만 유지하여 각 AnchorIdent.
  • 최종 SELECT

    :

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

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

원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿