[Graph] Union - Find

Union - Find 알고리즘

Union-Find 알고리즘은 Disjoint set을 확인, 표현하는 방법이다. 각 요소들이 같은 집합에 속하는지 확인할 수 있어 합집합, 그래프의 cycle 존재 여부를 확인하는데 사용할 수 있다.

Union-Find에서 각 집합은 tree로 표현된다. 트리 순회를 사용하여 두 정점이 같은 트리에 속하는지 판단하는 것이 아니라 각 정점의 부모 노드 정보를 저장하여 활용한다. 각 정점의 부모 노드 정보는 parent라는 배열에 저장되어 있다. parent 배열을 사용하면 자신의 부모로 이동하고, 다시 부모로 이동하는 과정을 통해 자신이 속한 트리의 루트 정점 정보를 확인 할 수 있다.

• getParent(parent, x) : 정점 x이 속한 집합의 루트 정점 정보를 반환한다.
• unionParent(parent, a, b) : 두 정점 a와 b가 속한 집합을 합친다.
• sameParent(parent, a, b) : 두 정점 a와 b가 같은 집합에 속하는지 판단한다.

일반적으로 위의 3가지 함수를 구현하면 Union-Find 알고리즘의 구현은 끝이다.

구현 코드

• parent 정보 초기화

	// parent init
	int* parent = new int[N + 1];
	for (int i = 0; i <= N; i++)
		parent[i] = i;

처음에는 모든 정점을 자기 자신만 있는 집합으로 만든다. 따라서 parent를 자기 자신으로 초기화 해준다.

• getParent 구현

int getParent(int* parent, int x)
{
	if (parent[x] == x) return x; // root인 경우
	
	parent[x] = getParent(parent, parent[x]); // parent update
	return parent[x];
}

parent 정보와 재귀를 활용하여 자신이 속한 집합의 root 정점을 찾는다. 부모의 정보가 자기 자신인 경우 root이므로 재귀를 종료한다. getParent 호출 시 parent에 저장된 부모 정보를 현재 자신이 속한 집합의 root로 업데이트하여 재귀 호출 횟수를 줄일 수 있다.

• unionParent 구현

void unionParent(int* parent, int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);

	// 더 작은 정점을 root로 설정
	if (a < b)
		parent[b] = a;
	else
		parent[a] = b;

}

우선 정점 a와 b가 속한 집합의 root를 찾는다. 이 코드는 두 집합을 합칠 때 더 작은 정점을 root로 사용한다. 따라서 합쳐져야 하는 정점의 parent 정보를 변경하여 두 집합을 같은 집합으로 합쳐준다. 이때 a(b)의 parent 값만 변경하면 a(b)를 root로 하는 모든 정점은 getParent 호출 시 재귀를 통해 새로운 root를 찾고, parent 정보가 업데이트 되기 때문에 a(b)의 parent 정보만 변경해 준다.

• sameParent 구현

bool sameParent(int* parent, int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);
	return a == b;
}

sameParent는 앞서 구현한 getParent 함수를 사용하여 쉽게 구현할 수 있다. 정점 a와 b가 속한 집합의 root를 getParent 함수를 통해 구한다. 그 뒤 두 root를 비교하여 같으면 같은 집합에 속하는지 판단한다.