분리 집합

분리 집합이란 교집합을 갖지 않는 집합들을 의미한다.

분리 집합은 원소 또는 개체가 "어느 집합에 소속되어 있는가?"라는 정보를 바탕으로 하는 알고리즘에 응용할 수 있다.

 

분리 집합의 표현

분리 집합을 표현할 때는 트리를 사용한다. 다만 분리집합에서 사용하는 트리는 일반적으로 부모가 자식을 가리키지 않고 자식이 부모를 가리킨다.

분리 집합을 이루는 트리 내의 모든 노드들은 루트 노드가 나타내는 집합 안에 있다.

 

분리집합의 연산

합집합

집합 탐색 연산

 

합집합

한 쪽 집합의 루트 노드를 다른 쪽 집합의 자식 노드로 만들면 된다.

집합 탐색

집합에서 원소를 찾는 것이 아니라 원소가 속해 있는 집합을 찾는 연산이다.

 

.h파일

#pragma once
 
#include<stdio.h>
#include<stdlib.h>
 
#ifndef DISJOINTSET_H
#define DISJOINTSET_H
 
typedef struct tagDisjointSet
{
    struct tagDisjointSet* Parent;
    void* Data;
} DisjointSet;
 
void DS_UnionSet(DisjointSet* Set1, DisjointSet* Set2);
DisjointSet* DS_FindSet(DisjointSet* Set);
DisjointSet* DS_MakeSet(void* NewData);
void DS_DestroySet(DisjointSet* Set);
#endif

.h파일을 구현한 cpp 파일

#include "DisjointSet.h"
 
void DS_UnionSet(DisjointSet* Set1, DisjointSet* Set2)
{
    Set2 = DS_FindSet(Set2);
    Set2->Parent = Set1;
}
 
DisjointSet* DS_FindSet(DisjointSet* Set)
{
    while (Set->Parent != NULL)
    {
        Set = Set->Parent;
    }
 
    return Set;
}
 
DisjointSet* DS_MakeSet(void* NewData)
{
    DisjointSet* NewNode = (DisjointSet*)malloc(sizeof(DisjointSet));
    NewNode->Data = NewData;
    NewNode->Parent = NULL;
 
    return NewNode;
}
 
void DS_DestroySet(DisjointSet* Set)
{
    free(Set);
}

테스트 파일

#include<stdio.h>
#include "DisjointSet.h"
 
int main(void)
{
    int a = 1, b = 2, c = 3, d = 4;
    DisjointSet* Set1 = DS_MakeSet(&a);
    DisjointSet* Set2 = DS_MakeSet(&b);
    DisjointSet* Set3 = DS_MakeSet(&c);
    DisjointSet* Set4 = DS_MakeSet(&d);
 
    printf("Set1 == Set2 : %d \n", DS_FindSet(Set1) == DS_FindSet(Set2));
    
    DS_UnionSet(Set1, Set3);
    printf("Set1 == Set3 : %d \n", DS_FindSet(Set1) == DS_FindSet(Set3));
 
    DS_UnionSet(Set3, Set4);
    printf("Set3 == Set4 : %d \n", DS_FindSet(Set3) == DS_FindSet(Set4));
 
    return 0;
}