분리 집합 (Disjoint Set)

분리 집합이란

서로 공통되는 원소를 가지지 않는 집합을 의미한다.

'교집합'이 존재하지 않는 집합 ('합집합만 존재한다.)

아래의 그림은 분리 집합의 예이다.

위의 분리 집합을 트리로 표현하게 되면 아래의 그림과 같이 나타낼 수 있다.

분리 집합의 트리 구조에서는 부모가 자식을 가리키지 않고 자식이 부모를 가리키는 방식으로 나타낸다.

루트 노드는 집합의 그 자체를 뜻하고 루트 노드 자신을 가리키는 모든 노드들은 그 집합에 속한다.

분리 집합의 연산

분리 집합의 연산에는 '합집합'이 있는데, 두 집합을 더하는 연산을 말한다.

트리 구조에서는 오른쪽 집합의 루트 노드를 왼쪽 집합 루트 노드의 자식 노드로 만들면 된다.

집합 탑색(Find) 연산

집합에서 원소가 속해 있는 집합을 찾는 연산

집합 내의 어떤 노드든 루트 노드가 나타내는 집합이 곤 자신이 속해 있는 집합이므로, 노드가 어떤 집합에 속해 있는지 알려면 이 원소가 속해 있는 트리의 루트 노드를 찾으면 된다.

부모 노드를 가리키는 포인터가 NULL인 노드가 루트 노드이다.

분리 집합 소스코드

#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

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

}