유니온 파인드 : JAVA

정의

어떤 그래프에서 서로 인접한 그래프가 있을때 특정 노드 u와 v가 서로 같은 그래프에 있는가를 판별할 때 사용하는 방법이다.

 

graph[i][j] = 1 이라는 것은 서로 연결되어 있다는 뜻이다. 만약 서로 연결되어 있다면 Union 두개의 노드를 같은 집합으로 합친다는 뜻이다.

이때 Find(i) Find(x) 를 하게 되는데 Find는 가장 위에 있는 부모의 값을 리턴하고 재귀과정에서 연결되 Node를 부모 노드에 바로 붙여준다.

이렇게 되면 처음 parent값은 한다리를 거쳐간다는것인데 이렇게되면 parent[x]의 값은 x가속한 집합이라고는 할수 없다. 하지만 각각에대해 Find를 돌리면 find가 재귀적으로 가장 부모노드에 연결시켜주므로 값이 제대로 나오는 것을 확인 할 수 있다.

 

소스코드

package test;
 
public class UnionFind {
    static int parent[];
 
    public static void main(String[] args) {
        // Uninon Find Test
 
        // 0 - 10 ,1 - 2 , 2 - 3 , 3 - 4, 5 - 6
        // 연결된 그래프에서 Union Find 구하기
        int graph[][] = new int[11][11];
        graph[0][10] = 1;
        graph[10][0] = 1;
        graph[1][2] = 1;
        graph[2][1] = 1;
        graph[2][3] = 1;
        graph[3][2] = 1;
        graph[3][4] = 1;
        graph[4][3] = 1;
        graph[5][6] = 1;
        graph[6][5] = 1;
 
        parent = new int[11];
 
        // 초기 parent는 자기 자신을 부모노드로 가진다.
        for (int i = 0; i <= 10; i++) {
            parent[i] = i;
        }
        
        for(int i=0;i<=10;i++) {
            for(int j=0;j<10;j++) {
                if(graph[i][j] == 1) {
                    Union(i,j);
                }
            }
        }
        
        // 잘합해졌는지 확인
        for (int i = 0; i <= 10; i++) {
            System.out.print(parent[i]+" ");
        }
        
        System.out.println();
        for (int i = 0; i <= 10; i++) {
            System.out.print(Find(i)+" ");
        }
        
        System.out.println();
        for (int i = 0; i <= 10; i++) {
            System.out.print(parent[i]+" ");
        }
    }
 
    public static void Union(int x, int y) {
        
        x = Find(x);
        y = Find(y);
        
        //서로 같은 부모가 아니라면 
        if (x != y) {
            parent[x] = y;
        }
 
    }
 
    public static int Find(int x) {
 
        if (x == parent[x]) {
            return x;
        } else {
            int pivot = Find(parent[x]);
            parent[x] = pivot;
            return pivot;
        }
    }
}
 

    static int parrent[];
    static int level[];
 
    static int Find(int x) {
        if (x == parrent[x])
            return x;
 
        int xx = Find(parrent[x]);
        return parrent[x] = xx;
    }
 
    static boolean Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        if (x == y) {
            return false;
        }
 
        if (level[x] > level[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }
 
        // y에 레벨이크다
 
        parrent[x] = y;
        if (x == y) {
            level[y]++;
        }
 
        return true;
    }