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

= Disjoint-Set 서로소 집합 알고리즘이라고도 불림.

 

그래프에서 여러 개의 노드 중 두 개의 노드를 선택해서 이 노드들이 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

 

- find : 노드의 부모가 같은지 확인하여 현재 같은 집합에 속하는지 확인하는 것

- union : 두 노드가 각각 포함되어 있는 집합을 합치는 것

 

1. 처음에 모든 노드들이 연결되어 있지 않을 때 -> 자기 자신이 부모

i	0	1	2	3	4	5
parent[i]	0	1	2	3	4	5

 

2. 1과 3, 2와 5가 각각 연결되어 있을 때

i	0	1	2	3	4	5
parent[i]	0	1	2	1	4	2

1과 3의 부모를 합쳐주고, 2와 5의 부모를 합쳐 준다(Union)

이 때는 더 작은 값으로 합쳐준다

 

3. 1-2-3처럼 연결될 때

i	0	1	2	3	4	5
parent[i]	0	1	1	2	4	5

- 처음에는 1과 2가 연결되며 2의 부모가 1이 되고, 2와 3이 연결되며 3의 부모가 2가 된다. 하지만 이 경우 1과 3이 같은 그래프에 속하는지 알 수 없으므로 재귀 함수를 통해 3의 부모인 2를 찾고, 2의 부모인 1을 찾아 3의 부모를 1로 설정해준다.(find) 그 결과 아래와 같다.

i	0	1	2	3	4	5
parent[i]	0	1	1	1	4	5

 

 

소스 코드

class Main {
    public static int[] parent = new int[100];

    public static int find(int x) {
        if (x == parent[x])   //부모가 자기 자신으로 설정되어 있는 경우
            return x;
        else
            return parent[x] = find(parent[x]);    //재귀를 통해 연결된 노드 중 가장 작은 값을 부모로 설정
    }

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x != y) {  //같은 부모가 아닐 때 합쳐준다
            if (x < y)  parent[y] = x;
            else parent[x] = y;
        }
    }

    public static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return true;
        else return false;
    }

    public static void main(String[] args) {
        for(int i = 1; i <= 8; i++) {
            parent[i] = i;
        }
        union(1, 2);
        union(2, 3);
        System.out.println("1과 3은 연결되어 있나요? " + isSameParent(1,3));
    }
}

 

 

 

참고

브랜든의 블로그 :: [알고리즘] 유니온 파인드 (Union-Find) (tistory.com)

[알고리즘] 유니온 파인드 (Union-Find)