(6)[Chapter4]분리집합_이론,코드구현

##분리집합 이론 노트 정리

Chapter4_4_1_분리집합_이론.pdf

1.07MB

##분리집합 코드 구현

Chapter4_4_2_분리집합_코드.pdf

1.97MB

 

 

#include <stdio.h>
#include <stdlib.h>
 
//분리 집합 구조체
typedef struct _DS_Set {
    struct _DS_Set* Parent;
    void* Data;
}Set;
 
//원소(1개짜리 원소 집합) 생성 메소드
Set* MakeSet(void* Data) {
    Set* newSet = (Set*)malloc(sizeof(Set));
    newSet->Data = Data;
    newSet->Parent = NULL;
 
    return newSet;
}
 
Set* FindSet(Set* set) {
    while (set->Parent != NULL) {
        set = set->Parent;
    }
 
    return set;
}
//합집합 연산 메소드
//=> 1_ A ∪ B , 2. A를 헤더로 적용한다.
void UnionSet(Set* A, Set* B) {
    
    //(1). B의 헤더 원소 찾아서, B에 반환
    B = FindSet(B);
 
    //(2). B의 헤더를 A로 대입
    B->Parent = A;
 
    return;
}
 
 
 
int main() {
 
    //집합 A의 원소
    Set* a = MakeSet(1);
    Set* b = MakeSet(2);
    Set* c = MakeSet(3);
    Set* d = MakeSet(4);
    
    //집합 B의 원소
    Set* e = MakeSet(5);
    Set* f = MakeSet(6);
    Set* g = MakeSet(7);
    
    //집합 C의 원소
    Set* h = MakeSet(8);
 
    //A = {a,b,c,d}
    UnionSet(a, b);
    UnionSet(a, c);
    UnionSet(a, d);
 
    //B = {e,f,g}
    UnionSet(e, f);
    UnionSet(e, g);
 
    printf("Set A == Set B : %d\n",FindSet(a)==FindSet(e));
    printf("Set A == Set B : %d\n",FindSet(a)==FindSet(c));
    printf("Set A == Set B : %d\n",FindSet(a)==FindSet(d));
 
    printf("-------------------------\n");
 
    UnionSet(a, e);//A∪B
 
    printf("Set A == Set B : %d\n", FindSet(a) == FindSet(e));
    printf("Set A == Set B : %d\n", FindSet(a) == FindSet(c));
    printf("Set A == Set B : %d\n", FindSet(a) == FindSet(d));
 
    return 0;
}