[#7] Disjoint Set (분리 집합)

분리 집합

사용 목적

데이터베이스에서 두 분리 집합을 취급하거나 서로 합집합을 만들어야하는 상황에서 사용된다. 이를테면 책을 관리하는 데이터베이스에서 책의 구조체의 변경없이 베스트셀러만 따로 모아두고 싶다한다면 책을 관리하는 트리의 루트 노드를 베스트셀러의 루트노드로 가리키면 된다. 

 

구조

분리 집합은 부모가 자식을 가리키는 일반적인 트리의 구조와 다르게 자식이 부모를 가리키는 구조이다.

 

 분리집합의 기능

분리 집합은 합집합(Union) 더하는 연산과 집합 탐색(Find) 연산이 있다.

 

---

 

전체 코드

DisjointSet.h

#ifndef DISJOINTSET_H
#define DISJOINTSET_H

#include <stdio.h>
#include <stdlib.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

 

DisjointSet.c

#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 );
}

 

Test_DisjointSet.c

#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;
}

 

---