Union Find 알고리즘

Kruscal 알고리즘을 공부하다보니,

Union Find 알고리즘 개념을 이해해야 하기때문에 우선 Union Find 알고리즘을 우선 정리하겠습니다.

 

목차
- Union Find란?
- Union Find 동작 방식 분석
- 코드 작성

 

 

1. Union Find란?

Union 이란 합집합이라는 뜻을 가지고 있습니다. 그래서 Union Find 알고리즘이란 합집합을 찾는 알고리즘
이라고 이해하면 될 것 같습니다.

주로 그래프 내에서 집합, 순환을 찾기 위해 사용합니다.

 

1-1 .먼저, 집합을 찾는 경우 입니다.

7개의 노드의 연결을 보여주는 그림을 봅시다.

그림 1. Union Find 알고리즘

 

이 경우 위 사진과 같이 2가지 그룹으로 나누어지는데, 이렇게 2가지를 찾아낼때 Union Find 알고리즘을 사용합니다.

 

2-2. 그리고 두번째로 순환 구조를 찾을때 사용합니다.

 

그림 2. 그래프에서 순환 찾기

 

위 그림처럼 왼쪽 그래프처럼 연결되어 있는 상태에서 3번 노드와 5번 노드를 연결한다면, 그림 2의 오른쪽 그림처럼
3,4,5는 순환이 되게 됩니다. 그리고 Union Find로 이런 순환을 찾아낼 수 있죠.

크루스칼 알고리즘의 경우 최소 비용으로 그래프를 연결해야 하기 때문에, 순환이 되면 안되는 조건이 있습니다.
이때 Union Find 알고리즘을 이용하는 것이죠!

 

 

2. Union Find 동작 방식 분석

UnionFind 알고리즘을 간단하게 정리하면
"각각의 노드의 부모가 동일하면 합집합, 그렇지 않으면 다른 집합"
이라고 판단하는 것 입니다.

알고리즘 구성은 아래와 같습니다.

1. 노드를 탐색하여 연결되어 있으면 부모 노드를 얻어온다.
2. 부모의 노드가 다르다면 둘 중 큰 번호의 부모 노드를 작은 번호의 부모 노드로 변경

그렇기 때문에 노드들의 부모를 작성해 줄 배열이 하나 필요합니다.
예제는 아래 그림 3 처럼 노드의 수는 7개, 2개의 집합으로 구분 가능한 그래프를 가지고 진행하겠습니다.

그림 3. 예제 그래프

 

 

우선 아래 그림과 같이 노드가 7개니까 길이 7의 parent 배열을 생성하고, 각각의 부보는 자기를 가르키도록 초기화 합니다.

그림 4. parent 배열 생성 및 초기화

 

1부터 시작해서 7까지 탐색합니다.

 

2-1. 노드 1 탐색

1) 1의 노드는 2와 연결되어 있기 때문에 부모 노드를 얻어옵니다.
그리고 1과 2의 부모 노드는 다르기때문에 2의 부모 노드를 1로 변경 합니다.

2) 1의 노드는 4와 연결되어 있기 때문에 부모 노드를 얻어옵니다.
그리고 1과 4의 부모 노드는 다르기때문에 4의 부모 노드를 1로 변경 하며 1의 탐색은 종료합니다.

그림 5.  노드 1 탐색

 

 

2-2. 노드 2 탐색

다음 2 노드를 탐색합니다.

1) 2는 1과 연결되어있습니다.
2) 부모노드를 얻어옵니다.
3) 2개의 노드 모두 부모 노드가 1로 동일 하기때문에 넘어갑니다.

 

2-3. 노드 3 탐색

3 노드를 탐색합니다.

1) 3의 노드는 4와 연결되어 있습니다.
2) 부모노드를 얻어옵니다.
3) 3의 부모와 4의 부모는 다르기 때문에 작은 노드로 변경합니다.
4) 그런데 3의 부모는 3, 4의 부모는 1이기 때문에 3의 부모 노드를 1로 변경합니다.

 

그림 6. 노드 3 탐색

 

2-4. 노드 4 탐색

노드 4는 1, 3 노드와 연결되어 있습니다.
부모의 노드를 얻어오는데, 둘 다 부모의 노드가 동일함으로 넘어갑니다.

 

2-5. 노드 5 탐색

노드 5는 6과 연결되어 있습니다.
둘의 부모 노드가 다르기때문에 6의 부모 노드를 5로 변경합니다.

그림 7. 노드 5 탐색

 

2-6 노드 6 탐색

노드 6은 5와 연결되어있지만 부모 노드가 동일함으로 넘어갑니다.
그리고 노드 7과도 연결되어있습니다.
노드 6과 7의 부모는 다르기때문에 노드 7의 부모를 6의 부모 노드인 5로 변경합니다.

그림 8. 노드 6 탐색

 

2-7. 마지막 노드 7 탐색

노드 7은 6과 연결되어있지만, 둘의 부모노드가 동일하기 때문에 넘어갑니다.

이렇게 프로그램은 종료되고 부모 노드는 아래와 같이 정리 됩니다.

 

그림 9. 종류 후 parent 표 상태

 

이렇게 종료가 된후 부모노드가 1인 그룹과 부모노드가 5인 그룹 이렇게 2개로 구성되어 있음을 알 수 있습니다.

이것이 Union Find 알고리즘 동작 방법입니다.

 

3. 코드 작성

코드로 작성하면 아래와 같습니다.

	//부모노드 찾기
	public int getParent(int parent[],int search) {
		if(parent[search] == search) return search;
		else
			return parent[search] = getParent(parent, parent[search]);
	}
	//합친 후 부모 노드 작은걸로 바꾸어주기
	public int[] changeParent(int parent[], int a, int b) {
		a = getParent(parent, a);
		b = getParent(parent, b);
		if(a<b) parent[b] = a;
		else parent[a] = b;
		
		return parent;
	}
	//부모 노드 찾기
	public boolean findParent(int parent[], int a, int b) {
		a = getParent(parent,a);
		b = getParent(parent,b);
		if(a==b) return true;
		else return false;
	}
    
	public static void main(String[] args) {
		UnionFind f = new UnionFind();
		int n = 8;
		
		int[][] graph = {{1,2},{1,4},{4,3},{5,6},{6,7}};
		int[] parent = new int[n];
		for(int i=1; i<n; i++) { parent[i] = i;}
        
        //부모 노드 바꾸기
        for(int i=0; i<graph.length; i++) {
			f.changeParent(parent, graph[i][0], graph[i][1]);
		}
        //부모 노드 출력
        for(int i=1; i<n; i++)
			System.out.print(parent[i] +" ");
     }

 

 

이 개념을 알면, 크루스칼 알고리즘은 아주아주 쉽게 이해하고 사용할 수 있습니다!