재귀 CTE를 사용하여 무방향 그래프에서 연결된 하위 그래프를 식별하는 방법은 무엇입니까?

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

문제:

무방향 그래프에서 연결된 노드 쌍을 나타내는 두 개의 열(식별자1 및 식별자2)이 있는 테이블에서 하위 그래프의 각 노드가 동일한 하위 그래프의 다른 모든 노드에 연결되도록 노드를 하위 그래프로 그룹화합니다.

해결책:

문제 설명의 원래 쿼리는 노드를 연결된 하위 그래프로 그룹화하는 재귀적 접근 방식을 사용하여 구체화할 수 있습니다. 다음은 재귀 CTE를 사용하여 그래프 가장자리를 순회하고 연결된 구성 요소를 식별하는 쿼리의 수정된 버전입니다.

<code class="sql">WITH RECURSIVE CTE AS (
    SELECT * FROM @T
    UNION ALL
    SELECT t2.Ident1, t2.Ident2 
    FROM CTE t1
    JOIN @T t2 ON t1.Ident2 = t2.Ident1
)
SELECT CTE.Ident, GroupID = MIN(CTE.Ident) OVER (PARTITION BY CTE.GroupPath)
FROM CTE
ORDER BY CTE.Ident</code>

작동 방식:

CTE라는 CTE(공통 테이블 표현식)는 입력 테이블 @T에서 모든 행을 선택하여 시작하는 재귀 쿼리 역할을 합니다. 그런 다음 UNION ALL 절이 그래프의 가장자리를 나타내는 CTE에 행을 추가하는 재귀적 합집합을 수행합니다. 구체적으로, t1.Ident2가 t2.Ident1과 같다는 조건으로 CTE를 입력 테이블 @T와 조인하여 각 노드에서 그래프의 가장자리를 효과적으로 통과합니다.

연결된 하위 그래프를 식별하기 위해 쿼리는 CTE의 GroupPath 열을 활용합니다. 이 열은 재귀 순회 중에 발견된 식별자의 누적 경로로 계산됩니다. CTE를 GroupPath로 분할하고 MIN(CTE.Ident) OVER (PARTITION BY CTE.GroupPath)를 사용하여 각 파티션 내의 최소 Ident 값을 선택함으로써 노드를 연결된 하위 그래프로 그룹화합니다.

예 :

다음 입력 테이블을 고려하세요.

Identifier1	Identifier2
a	c
b	f
a	g
c	h
b	j
d	f
e	k
i	NULL
c	b

수정된 쿼리를 실행하면 다음 결과가 생성됩니다.

Identifier	GroupID
a	1
b	2
c	1
d	2
e	3
f	2
g	1
h	1
j	2
k	3
l	4

이 예에서는 노드 " a", "c", "g" 및 "h"는 GroupID=1인 하나의 연결된 하위 그래프를 형성하고, 노드 "b", "d", "f" 및 "j"는 GroupID=2인 또 다른 하위 그래프를 형성합니다. 노드 "e"와 "k"는 GroupID=3인 별도의 하위 그래프에 있고 노드 "i"는 GroupID=4인 자체 하위 그래프에 있습니다(다른 노드와 연결되지 않기 때문입니다).

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