알고리즘 : 최소 신장트리1-2

알고리즘 : 최소 신장트리1-2

728x90

Union-Find 알고리즘

Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘

노드들 중에 연결된 노드를 찾거나 노드들을 서로 연결할 때(합칠 때)사용

Disjoint Set은?

- 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

- 공통 원소가 없는(서로소) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조

- Disjoint Set = 서로소 집합 자료구조

1. 초기화

n개의 원소가 개별 집합으로 이뤄지도록 초기화

A B C D E F

2. Union

두 개별 집합을 하나의 집합으로 합침(두 트리를 하나의 트리로 만듦)

3. Find

여러 노드가 존재할 때 두 개의 노드를 선택해서 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 각 그룹의 최상단 루트 노드를 확인

Union-Find 알고리즘의 고려할 점

Union 순서에 따라서 최악의 경우 링크드 리스트와 같은 형태가 될 수 있음

Find/Union시 계산량이 O(N)이 될 수 있으므로 해당 문제를 해결하기 위해 union-by-rank, path compression 기법을 사용함

from http://every-time-i-pass-this-place.tistory.com/32 by ccl(A) rewrite - 2021-10-09 13:27:13