합집합 찾기 알고리즘(Union-Find Algorithm)

유니온 파인드 알고리즘은 여러 개의 노드가 존재할 때 두 개의 노드를 선택하여 서로 같은 그래프에 속해 있는지

 

판별하는 그래프 알고리즘이다.

 

Union-Find Algorithm

그림과 같이 부모를 합칠 때 일반적으로 더 작은 값 쪽으로 합친다. 그림에 대해 구체적으로 설명하자면,

 

(1) 노드가 모두 연결되지 않은 상태에서의 각 노드의 부모노드는 자기 자신을 가리킨다.

 

(2) 1과 2를 연결하면 2의 부모노드는 더 작은 값인 1 이다.

 

(3) 2와 3을 연결하면 3의 부모노드는 더 작은 값인 2 이지만, 재귀 함수를 통해 결과적으로 1이 부모노드가 된다.

 

[예제]

#include <stdio.h>

int getParent(int parent[], int x) {
	if(parent[x] == x) return x;
	return parent[x] = getParent(parent, parent[x]);
}

int unionParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if(a < b) parent[b] = a;
	else parent[a] = b;
}

int findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if(a == b) return 1;
	return 0;
}

int main() {
	int parent[11];
	for(int i=1; i<=10; i++) {
		parent[i] = i;
	}
	unionParent(parent, 1, 2);
	unionParent(parent, 2, 3);
	unionParent(parent, 3, 4);
	unionParent(parent, 5, 6);
	unionParent(parent, 6, 7);
	unionParent(parent, 7, 8);	
	printf("1과 5는 연결되어 있나요? %d\n", findParent(parent, 1, 5));
	unionParent(parent, 1, 5);
	printf("1과 5는 연결되어 있나요? %d\n", findParent(parent, 1, 5));
}

 

위 소스코드에서 getParent() 함수는 부모 노드를 찾는 함수이며, 부모노드가 자기자신이라면 자기자신을 반환한다.

 

그렇지 않을 경우 재귀호출하여 부모 노드를 찾는다.

 

unionParent() 함수는 두 부모 노드를 합치는 함수이며, 각 부모노드 값을 비교한 뒤에 더 작은 값 쪽으로

 

부모노드를 합친다. 즉, 변수 b가 더 크다면 b의 부모 값이 a가 되고, a가 더 크다면 a의 부모 값이 b가 될 수 있도록 한다.

 

findParent() 함수는 같은 부모를 가지는지 확인하는 함수이며, 각 부모노드 값을 비교한 뒤에 같다면 1을,

 

같지 않다면 0을 반환한다.

 

메인코드에서 자기자신을 부모로 가리키도록 10개의 데이터를 넣고 unionParent() 함수를 통해 원소를 한다.

 

첫번째 출력문에서 1과 5가 같은 부모를 가지는지 출력할 경우 0 즉, False를 반환하는데, 아래 그림과 같이

 

1의 부모노드는 1, 5의 부모노드는 5이기 때문이다.

 

 

unionParent() 함수를 통해 1과 5를 합쳐준 후 다시 출력하면 1 즉, True를 반환하는 것을 확인할 수 있다. 

 

[결과]

Union-Find 결과

 

---

출처

https://blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)