[Algorithm] Union-Find

Union-Find

---

Union-Find 알고리즘은 서로소인 부분집합(그래프)을 표현하기 위한 알고리즘이다. union(x, y), find(x) 연산으로 이루어져 있으며 union(x, y)는 노드 x와 노드 y를 루트노드로 가지는 각 집합을 합하는 연산을 의미하고 find(x)는 x가 속한 집합의 루트노드를 확인하는 연산을 의미한다. Union-Find 알고리즘을 구현하기 위해서 필요한 자료구조는 각 노드의 부모노드를 저장하기 위한 배열이 필요하다.

 

 

Union-Find 코드

---

public class Main {
    private static int[] parent;

    public static void main(String[] args) {
        parent = new int[N+1];

        //union-find에 사용할 parent배열 초기화
        for(int i=1; i<=N; i++) parent[i] = i;
    }

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

        //노드 번호를 기준으로 부모노드 재설정
        if(x >=) parent[ry] = rx;
        else parent[rx] = ry;
    }

    public static int find(int x) {
        //부모노드가 자기 자신이라면 -> root 노드라면
        if(parent[x] == x) return x;
        return find(parent[x]);
    }
}

 

 

Reference

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