[CS] 서로소 집합 (JAVA)

서로소 집합

교집합이 공집합인 집합(서로소 집합)들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조

- Union 연산

• 어떤 두 원소 a, b 에 대해서, union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산이다.
• \(a \in A, b \in B\) 에 대해서, union(a, b)는 \(A \cup B\) 이다.

- Find 연산

• 어떤 원소 a에 대해서, find(a)는 a가 속한 집합(집합의 대표번호)을 반환하는 연산이다.
• \(a \in A\) 에 대해서, find(a)는 집합 A(집합 A의 대표번호)를 반환한다.

 

서로소 집합의 표현

- 초기화

출처 : https://sskl660.tistory.com/71

- Union 연산
    ex) union(1, 2)

출처 : https://sskl660.tistory.com/71

- Find 연산
    ex) find(3) = 1, find(5) = 1

출처 : https://sskl660.tistory.com/71

 

서로소 집합의 구현

void union(int[] parent, int element1, int element2) {
    // element1과 element2의 대표 노드 확인
    int root1 = find(parent, element1);
    int root2 = find(parent, element2);

    // element1과 element2의 대표 노드가 다를 경우
    if (root1 != root2)
        parent[root1] = root2;
}

int find(int[] parent, int element) {
	// 찾는 대상과 인덱스 번호가 같다면 그 인덱스가 해당 집합의 부모이다
    if (parent[element] == element)
        return element;
    else {
    	// 해당 인덱스가 가리키는 값(부모 노드)을 따라 최종 부모 노드까지 탐색
        return parent[element] = find(parent, parent[element]);
    }
}