목록집합 (1)

algoqna

Disjoint-Set (상호 배타적 집합) - 트리 이용

Union-Find 1) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 ● 0 ~ n-1 까지의 원소로 표현한 뒤, 각 1개의 원소를 포함하는 n개의 집합을 만들어야 함 = 배열 선언 2) 필수적인 세 가지 연산 ● 초기화 : n개의 원소가 집합에 포함되어 있도록 초기화 ● Union(a,b) : 원소 a와 b를 하나로 합친다 == 두 집합을 하나의 집합으로. ● find(a) : 원소 a가 속한 집합을 반환한다. 3) 트리를 이용한 상호 배타적 집합 ● 한 집합에 속하는 원소들을 '하나의 트리'로 묶는다 ● 그리하여 상호 배타적 집합은 '트리들의 집합' ● 어떤 정점 v와 u가 같은 집합인지 알고싶다? * 정점 v와 u가 '같은 루트' 를 공유하고 있나를 확인한다...
자료구조 2023. 2. 27. 23:57
이전 Prev 1 Next 다음