Union - Find 알고리즘 (Java )

Union - Find 

• 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다
• 상호 배타적 집합이라고도 합니다
• 여러 노드가 존재할때, 두 개의 노드를 선택해서 현재 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘입니다
• Find와 Union이라는 두가지 연산으로 이루어져 있습니다

예제

• 연결되지 않을 경우, 자신 자신을 가르키도록 합니다

• 부모를 합칠 경우에는, 더 작은쪽 값으로 합칩니다
• 이것을 합침 과정이라고 합니다

• 1과 3은 부모가 다르기 때문에 '1과 3이 연결되었는지' 파악하기에 힘이 듭니다
• 이때, 재귀함수가 사용됩니다

public static int[] parent = new int[1000001];

public void find_union_algorithm() {
    for (int i =0; i  <= 8; i++) {
        parent[i] = i;
    }
    union(1,2);
    union(2,3);
}

public 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 int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}