◇ Union-Find 데이터 구조(disjoint set 데이터 구조)
서로소 집합: 공통 요소가 없는 두 집합
두 가지 유형의 작업이 지원됩니다.
합집합: 두 개의 요소가 있는 집합을 하나의 집합으로 결합하는 작업입니다.
찾기(Find): 특정 요소가 어떤 집합에 속하는지를 나타내는 연산.
– 운영 프로세스
1. 결합 동작을 확인하여 두 노드 A와 B가 함께 연결되어 있는지 확인
1.1 각각 A와 B의 루트 노드 A’와 B’를 찾습니다.
1.2 A’를 B’의 부모 노드로 만들기
2. 모든 통합 작업이 처리될 때까지 1단계를 반복합니다.
ex) 합집합(1,4) 합집합(2,3) 합집합(2,4) 합집합(5,6)
0. 노드의 수와 크기로 상위 테이블을 초기화합니다.
1. 노드 1과 노드 4의 루트 노드를 각각 찾아 현재 루트 노드가 각각 1과 4이므로 더 큰 숫자에 해당하는 루트 노드 4의 부모 노드를 1로 설정합니다.
2. 노드 2와 노드 3의 루트 노드를 각각 찾습니다. 현재 루트 노드는 각각 2와 3이므로 더 큰 루트 노드 3의 부모 노드를 2로 설정합니다.
3. 노드 2와 노드 4의 루트 노드를 각각 찾아 현재 루트 노드가 각각 2와 1이므로 더 큰 숫자에 해당하는 루트 노드 2의 부모 노드를 1로 설정합니다.
4. 노드 5와 노드 6의 루트 노드를 각각 찾습니다. 현재 루트 노드는 각각 5와 6이므로 더 큰 루트 노드인 6의 부모 노드를 5로 설정합니다.
– 집합의 형태는 연결성으로 확인할 수 있음 > 연결된 노드는 동일한 집합임 > 위의 예는 두 집합
>> 루트 노드를 찾는 것은 부모 테이블을 계속해서 확인하고 다시 돌아가야 하는(재귀적으로) 불편함이 있습니다.
– 기본 구현 방법에 대한 의사 코드
#주어진 요소가 속한 집합을 찾는 방법 find_parent
# 루트 노드를 찾을 때까지 재귀 호출
# 두 요소가 속한 세트를 조인하는 Union_parent 메소드
# 루트 노드를 찾아 큰 쪽을 작은 쪽과 병합 == 루트 노드 업데이트
# 꼭짓점 수와 가장자리 수에 대한 입력 받기(합집합 연산)
# 부모 테이블을 0으로 초기화
# 부모 테이블에서 자신과 함께 부모 초기화
# 노조 작업을 수행
# 각 요소가 속한 집합을 인쇄합니다.
# 부모 테이블의 내용 출력
– 경로 압축 기술
조회 함수를 재귀적으로 호출한 직후에 상위 테이블의 값을 업데이트합니다.
– 서로소 집합이 있는 주기 구분
: 무방향 그래프에서 순환을 결정하기 위해 서로소 집합을 사용할 수 있습니다.
방향 그래프에 주기가 있는지 여부는 DFS를 사용하여 확인할 수 있습니다.
– 주기 판별 알고리즘
1) 각 엣지를 개별적으로 확인하고 두 노드의 루트 노드 확인
1.1 루트 노드가 다른 경우 두 노드에서 합집합 연산 수행
1.2 루트 노드가 다르면 사이클이 발생한 것입니다.
2) 모든 가장자리에 대해 1단계를 반복합니다.
– 의사 코드
#find_parent
#union_parent
# 꼭짓점 수와 가장자리 수에 대한 입력 받기(합집합 연산)
# 부모 테이블을 0으로 초기화
# 부모 테이블에서 자신과 함께 부모 초기화
# 주기 발생 여부는 false로 초기화됩니다.
# 모든 모서리에 적용
# 주기가 발생하면 종료
# 순환이 발생하지 않으면 합집합을 실행합니다.