서로소 집합 데이터 구조_Abstract Data Type

안녕하세요. 부산 공수니 입니다! 오늘은 서로소 집합 데이터 구조에 대해 알아보겠습니다.

 

그리디(Greedy) 알고리즘에서 크루스칼(kruscal) 알고리즘에서는 초기 자기자신의 마디(vertex))만 포함된 서로소 부분집합들을 만들고 모든 마디들이 같은 집합에 속할 때까지 되풀이 하여 부분 집합을 합병(merge) 합니다. 이 알고리즘 구현을 위해 서로소 집합에 대한 데이터 구조가 필요합니다. 

 

추상 데이터구조(abstract data type)은 데이터 객체와 그 객체에 대한 연산으로 이루어집니다. 

 

여기선 U 라는 구성요소의 전체영역(universe) 로 시작합니다. ( 글씨가 이쁘지 못한 점 양해 부탁드립니다.) 

이 멤버로 부터 집합을 만드는데 필요한 프로시저가 makeset입니다. 

for(each x E U)
	makeset(x);

 

p,q 는 set_pointer 타입입니다. 집합을 가리키는 포인터라는 의미가 되기 위해 find 라는 함수와 함께 정의해야합니다. 

p = find('B'); //B가 포함된 집합을 가리키는 포인터
q = find('C'); //C가 포함된 집합을 가리키는 포인터

두개의 집합을 하나로 합병하는 프로시저 merge 도 필요합니다. 

(a) 5개의 서로소 집합, p= find(B)와 q = find(C) 실행
	{A},{B}<-p,{C}<-q,{D},{E}
    	 
(b) {B}와 {C}를 합병 후에는 4개의 서로소 집합 존재
	{A},{B,C},{D},{E}
    
(c) p=find(B)를 실행 
	{A},{B,C}<-p,{D},{E}
    	  

 

마지막을 두 집합이 동일한지 검사하는 equal이 필요합니다. 맞으면 True, 틀리는 false 를 반환합니다. 

 

 

-객체 : 전체 집합의 원소들과 그 원소들의 서로소 집합으로 구성

-연산 : find, merge, equal,make-set 

 

 

 

 

---

 

서로소 집합을 표현하는 한 가지 방법은 역포인터(inverted pointer)를 가진 트리를 사용하는 것입니다. 이게 무슨 소리냐면 이 트리는 뿌리 마디가 아닌 마디의 포인터는 그의 부모 마디를 가리키고 뿌리마디는 자기 자신을 가리킵니다.

 

간단 구현을 위해 인덱스를 정수로 하겠습니다. 

여기서 U의 각 인덱스는 전체 집합의 하나의 인덱스를 나타낸다는 점을 생각해보면 

 

- 인덱스 i가 뿌리마디가 아니면 U[i] 값은 그 마다의 부모마디 인덱스

- 인덱스 i가 뿌리면 U[i] = i 

 

초기화 할때는 다 뿌리마디이기 때문에 모든 i가 U[i] = i 입니다. 

예를 들어 확인해봅시다.

초기화 후 

 

여기서 집합 {4}와 {10}이 합병된다면 10이 포함된 마디가 4를 포함된 마디의 자식마디가 됩니다.

U[10] 도 부모마디인 4로 바뀐다. 

다음은 여러 합병을 걸친 결과 입니다. 트리의 구조는 합병순서에 따라 변화합니다. 

 

다음과 같이 할 수 있겠죠. 편의를 위해 중괄호를 제외하겠습니다.

1. 4와 10 합병

2. 4와 7 합병

3. 2와 4 합병

. . . .

 

 

다음 코드는 서로소 집합 데이터구조1 를 구현하기 위한 슈도코드입니다. 

 

const int n = 전체집합이 가지는 요소의 개수;

typedef int index;
typedef index set_pointer;
typedef index universe[1..n];

universe U; //전체집합

void makeset (index i) {
	U[i] = i;
}

set_pointer find(index i){
	index j;
    while(U[j]!=j)
    	j = U[j];
    return j;
}

void merge(set_pointer p,set_pointer q){
	if(p < q)
    	U[q] = p;  //p는 더 이상 집합을 가리키는 포인터가 아님
    else
    	U[p] = q;  //q는 더 이상 집합을 가리키는 포인터가 아님
}

bool equal(set_pointer p, set_pointer q){
	if(p == q)
    	return true;
    else 
    	return false;
}

void initial(int n){
	index i;
    
    for(i = 1; i <= n; i++)
    	makeset(i);
}


    

 

이 데이터 구조에서 반복문을 가지고 있는건 find 함수 뿐입니다. 그럼으로 시간 복잡도 차수는 find 함수에 의해 지배적입니다. initial 의 시간복잡도는 명백히 n 입니다.(n과 m은 구분해줄 필요가 있습니다.)

 

그럼 최악의 find 상황을 고려해 보겠습니다.

합병의 결과로 나온 트리의 깊이가 전체 마디 개수보다 한개 작으면 최악의 경우 입니다. 

 

 

그럼 이러한 경우가 발생하지 않도록 merge 을 수행하면 효율이 상승합니다. 각 트리의 깊이를 추적하고 비교하면 됩니다. 새로운 합병 방식으로 깊이가 작은 트리가 나온다는 사실에 주목합시다. 

 

 

 

const int n = 전체집합이 가지는 요소의 개수;

typedef int index;
typedef index set_pointer;

//구조체 선언 
struct nodetype{
	index parent;
    int depth; // 깊이 추가 
}
typedef index universe[1..n];

universe U; //전체집합

void makeset (index i) {
	U[i].parent = i;
	U[i].depth = 0;
}

set_pointer find(index i){
	index j;
    while(U[j].parent!=j)
    	U[j].parent;
    return j;
}

void merge(set_pointer p,set_pointer q){
	if(U[p].depth == U[q].depth){
    	U[p].depth = U[q].depth +1;
        U[q].parent = p;
    }else if(U[p].depth < U[q].depth)
    	U[p].parent = q;
    else
    	U[q].parent = p;
}

bool equal(set_pointer p, set_pointer q){
	if(p == q)
    	return true;
    else 
    	return false;
}

void initial(int n){
	index i;
    
    for(i = 1; i <= n; i++)
    	makeset(i);
}


    

이렇게 서로소 집합 데이터를 살펴보았습니다. 

 

오늘도 수고하셨습니다.