[허언증/Algorithm] Union_Find 합집합 찾기 (node find Algorithm)

안녕하세요. 허언증입니다.

 

Union_Find에 대해 알아봅시다

여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다.

 

1. Find (부모 노드를 찾는다)

2. Union ( 두 개의 노드를 하나의 부모노드로 만들어준다)

 

 

1~9번 Node가 있습니다.

각 번호는 현재 각자의 번호를 부모노드로 인식하고 있습니다.( 자기자신이 부모노드로 인지)

 

 

 

 

만약 2번이 1번과 연결을 한다면 2번의 부모노드는 1번이 됩니다.

(단. 둘 중 더 작은번호가 부모노드 우선권이 있다고 가정할 때)

그런데 3개이상 연결이 될 땐 신경써줘야 할 부분이 생깁니다.

 

 

이처럼 3번째 노드의 부모는 1이 되어야 하지만 2로 지정되어 있습니다.

이 문제점을 해결하기 위해선 재귀함수를 이용해서 부모노드를 1번으로 찾을수 있게 코드작성을 합니다.

현재 과정은 Union_Find 알고리즘에서 Find 부분이며 이어서 Union 부분을 설명하겠습니다.

 

Find로 부모노드를 찾았다면 이제 밑에 있던 표처럼 두 부모노드를 합치는 함수가 필요하겠죠?

Union은 두 부모노드를 합치기 때문에 소스를 참고하시면 될 듯 합니다!

#include <stdio.h>

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

// 각 부모 노드를 합칩니다. 
void 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;
	else return 0;
}

int main(void) {
	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));
}

출처_https://blog.naver.com/ndb796/221230967614

 

Union_Find.cpp

0.00MB