[알고리즘] 서로소 집합(Disjoint-sets) - Java

[알고리즘] 서로소 집합(Disjoint-sets)

 

서로소 or 상호배타 집합

서로 중복 포함된 원소가 없는 집합

(= 즉, 교집합이 없는 것)

 

대표자(representative)

집합에 속한 하나의 특정 멤버를 통해서 각 집합들을 구분

 

상호배타 집합 표현 방법

연결 리스트

트리

 

상호배타 집합 연산

Make-Set(x), Find-Set(x), Union(x,y)

 

트리를 이용해 상호배타 집합 표현된 모습

부모는 해당 노드의 Find-Set 값

 

연산

Make_Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산

Find_Set(x) : x를 포함하는 집합을 찾는 연산(해당 노드의 부모 정보 갱신)

Union(x,y) : x와 y를 포함하는 두 집합을 통합하는 연산

 

Make_Set(x)

public static void makeSet(int x){
    parent[x] = x; // 부모 : 자신의 index로 표시
}

Find_Set(x)

public static int findSet(int x){
    if(x == parent[x])
        return x;
    else {
        parent[x] = findSet(parent[x]);
        
        return parent[x];
    }
}

Union(x,y)

public static void union(int x, int y) {
    int px = findSet(x);
    int py = findSet(y);
    
    if (px != py){
        parent[py] = px;
    }
}

전체 소스 코드

/*
 *  상호배타 집합 => MST (크루스칼 알고리즘에 활용)
 *  makeSet(int x) 멤버 x를 포함하는 새로운 집합을 생성
 *  findSet(int x) 멤버 x를 포함하는 집합의 대표자를 리턴
 *  union(int x, int y) 멤버  x,y의 대표자를 구해서 두 집합을 통합
 *  link(int px, int py) x의 대표자의 집합과 y의 대표자의 집합을 합침
 */
 
public class Disjoint_sets {
 
    static int[] parent = new int[10]; // 부모 저장 배열
    static int[] rank = new int[parent.length]; // 랭크 저장 배열
    
    
    public static void main(String[] args) {
        
        for (int i = 0; i < parent.length; i++) {
            makeSet(i);
        }
        
        printSet();
        union(0, 1); printSet();
        union(3, 5); printSet();
        union(0, 3); printSet();
    }
 
    public static void printSet() { // 출력
        System.out.print("index : ");
        for (int i = 0; i < parent.length; i++) {
            System.out.print(i + " ");
        }
        System.out.println();
        
        System.out.print("parent : ");
        for (int i = 0; i < parent.length; i++) {
            System.out.print(parent[i] + " ");
        }
        System.out.println();
        System.out.println();
    }
    
    public static void makeSet(int x){
        parent[x] = x; // 부모 : 자신의 index로 표시
    }
    
    public static int findSet(int x){
        if(x == parent[x])
            return x;
        else {
            parent[x] = findSet(parent[x]);
            
            return parent[x];
        }
    }
    
    public static void union(int x, int y) {
        int px = findSet(x);
        int py = findSet(y);
        
        if (px != py){
            parent[py] = px;
        }
    }
}
 

이와 같은 연산을 활용해 MST(최소 신장트리), Prim이나 KRUSKAL 알고리즘에서 적용시킬 수 있다.