1. 유니온 파인드 (Union Find : 합 찾기), 병합 찾기 집합 (Merge Find Set)
ㅇ 주로, 그래프 내 서로소 (상호배타적) 집합의 원소들을 관리(저장,조작 등)하는 자료구조
ㅇ 구현에 필요한 연산
- 초기화 또는 생성 : make-set(x), 상호배타적인 집합 생성 (원소 x로만 이루어진 집합)
- Union 연산 : union(x,y), 원소 x를 갖는 집합과 y를 갖는 집합을 하나로 합침
- Find 연산 : find-set(x), 원소 x를 갖는 집합을 찾음
ㅇ 구현용 자료구조 : 주로, 연결 리스트,트리 등을 이용
ㅇ 연결 리스트에 의한 구현
- 매 서로소 집합을 연결 리스트로 구현
- 각 원소 마다 2개 포인터로, 하나는 다음 원소, 또하나는 대표 원소를 가리킴
- 대표 원소는 맨 앞에 있는 원소로써,
. 1개 포인터는 자기자신을 가리킴
. 처음 생성시 즉,make-set(x) 경우에, 다음 원소에 대한 포인터는 NULL로 해둠
- 마지막 원소를 가리키는 tail 이라는 변수를 둠
ㅇ 응용 例)
- 최소신장트리를 위한 크루스칼 알고리즘 등