[자료구조] Union Find 알고리즘 : 재귀호출 (Java)

Union Find 알고리즘이란?

 

Union Find 알고리즘은 크루스칼 알고리즘의 구현을 위한 핵심 자료구조로

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

 

말로써는 이해가 어려울수 있으니 그림으로 설명을 하겠다.

 

위처럼 3개의 노드가 존재하고 있다고 가정하자. 각각의 노드들은 아직 연결되어 있는것이 없기 때문에 

각각의 부모노드는 자기 자신이다.

그래서 위의 노드의 부모 노드표를 보면 아래와 같다.

 

1	2	3
1	2	3

 

 

위의 상황에서 우리는 1-2 를 서로 연결하고 싶다고 할때 그래프는 아래와 같이 변하고

표는 아래와 같이 변하게 된다.

1	2	3
1	1	3

( 보통 위처럼 노드를 연결하게 될때 부모 노드는 수가 작은쪽의 노드를 수가 큰쪽의 부모노드에 넣는다. ) 

 

그리고 우리는 이제 2-3의 노드를 연결하고 싶을때 그래프는 아래와 같이 변하고

표는 아래와 같이 변한다.

1	2	3
1	1	2

 

하지만 2번의 부모 노드는 1번이므로 3번의 부모 노드도 1번으로 변경해주어야 한다.

그래서 우리는 이부분에서 재귀호출을 하게 된다.

 

아래와 같이 3번의 부모노드인 2번의 부모 노드를 호출하고

2번에선 1번의 부모노드를 호출해서 

1번에서 부모노드의 값인 1을 returnt해서 받아서 결국엔 표가 아래와 같이 변한다.

 

1	2	3
1	1	1

 

그래서 그래프도 결국 아래와 같이 변하게 된다.

 

 

위의 과정을 소스로 보면 아래와 같다.

 

UnionFind Class

public class UnionFind {
	//일단은 노드를 연결해주는 부분이 있어야 한다.
	public void union(int x, int y, int[] parent) {
		x = find(x, parent);
		y = find(y, parent);
		
		if(x!=y) {
			//x와 y의 부모노드값이 서로 다르면 같아지게 이어줘야 한다.
			//이어주는 부분에서 주의해야 할점은 노드들을 오름차순으로 정렬후에 먼저 받는 x의 값이 y값보다 작아야 한다.
			parent[y] = x;
		}
	}
	
	//여기선 부모 노드의 값을 리턴해주면 된다.
	private int find(int x, int[] parent) {
		// TODO Auto-generated method stub
		//주의해야할점은 부모 노드의 값과 전달 받은 값이 상이 하다면 해당 부모의 노드를 다시 받아와야 한다.
		if(x == parent[x]) {
			return x;
		}else { 
			//내 노드와 받은 노드의 값이 다르다면 부모 노드에 다른 값이 들어갔다는건데 그 값의 부모노드를 알기위해선 
			//parent[x] 안에 있는 값의 부모노드값을 받아와야 한다. 
			return find(parent[x],parent);
		}
	}
}

 

main 함수

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		PreTest p = new PreTest();
		
		int n = 7;
		int[] parent = new int[n];
		
		//노드의 부모를 자기로 지정해서 배열을 생성함
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        UnionFind uf = new UnionFind();
        
        uf.union(0, 1,parent);
        uf.union(1, 2,parent);
        
        System.out.println(Arrays.toString(parent));


	}