서로소 집합 : Disjoint - Set

정의

서로소 또는 상호 배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 교집합이 없다.

• 대표자(Representative)
• 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분

표현 방법

• 연결 리스트

• 트리

연산

• Make-Set(x)
• x를 원소로 갖는 최소 단위 집합 만들기

• Find-Set(x)
• x를 원소로 갖는 집합 찾기 → 대표자를 반환

• Union-Set(x, y)

구현

연결리스트

• 같은 집합의 원소들은 하나의 연결리스트로 관리

• 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.

• 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다.

트리

• 같은 집합의 원소들을 하나의 트리로 표현

• 자식 노드가 부모 노드를 가리키며, 루트 노드가 대표자가 된다.

// Make-Set
// 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
void makeSet(int x) {
		p[x] = x;
}

// Find-Set
// x를 포함하는 집합을 찾는 연산
void findSet(int x) {
		if (x == p[x]) {
				return x;
		}
		else {
				return findSet(p[x]);
		}
}

// Union-Set
// x와 y를 포함하는 두 집합을 통합하는 연산
void unionSet(int x, int y) {
		if (findSet(y) == findSet(x)) {
				return;
		}

		p[findSet(y)] = findSet(x);
}

최적화

Rank를 이용한 Union

각 노드는 자신을 루트로 하는 Subtree 높이를 Rank로 저장한다.

• 두 집합을 합칠 때, Rank 높은 집합에 붙이기

경로 압축 : Path Compression

Find-Set 할 때, 모든 노드들의 포인터가 root를 가리키도록 변경해주기

void findSet(int x) {
		if (x == p[x]) {
				return x;
		}
		else {
				return p[x] = findSet(p[x]);

응용

• 최소신장트리(MST)
• Kruskal Algorithm

출처