Union-Find 알고리즘

Union-Find (유니온 파인드, disjoint set) 알고리즘 이란?

집합을 관리하는 자료구조 , 상호 배타적 집합(disjoint set)이라고도 한다.

• Find : 노드 X가 어느 집합에 포함되어 있는지 찾는 연상
• Uinon : 노드 X가 포함된 집합과 노드 Y가 포함된 집합을 합치는 연산

Union-Find 그림으로 이해하기

node는 4개로 구성되어 있고,
parent[node]는 부모 노드번호로 가정할 때 그림으로 아래와 같이 표현했다.

Union-Find 코드로 이해하기

public static int[] parent;     // 부모노드

public static void main(String args[]){
    int[] arr = new int[4];
    parent = new int[4];

    // 4개의 노드, 부모노드 초기화
    for(int i=0;i<4;i++){
        arr[i] = parent[i] = i;
    }

    union(1,2);
    System.out.println("2의 부모 :" +find(2)+" / 3의 부모 :" +find(3));
    union(2,3);
    System.out.println("3의 부모 :" +find(2));

}

// find 함수
public static int find(int n){
    // 부모가 자기 자신인 경우
    if(parent[n] == n ){
        return n;
    }else{
        // 재귀함수를 이용하여 부모를 추적
        return parent[n] = find(parent[n]);
    }
}

// union 함수
public static void union(int n1, int n2){
    // n1과 n2를 합치기 전에 부모부터 찾아야 한다.
    n1 = find(n1);
    n2 = find(n2);

    // 대게, 부모를 합칠때는 일반적으로 더 작은값쪽을 합친다.
    if(n1 != n2){
        // n2 > n1
        // 부모가 다르다면 n2의 부모를 n1으로 설정
        if(n2 > n1){
            parent[n2] = n1;
        }else{
            parent[n1] = n2;
        }
    }
}

전체 소스보기(git)

[참조]

[JAVA 자료구조] 유니온 파인드(Union Find) / 서로소 집합 (Disjoint Set)
[알고리즘] 유니온 파인드 (Union-Find)