서로소 집합 (disjoint-set) data structure algorithm

크루스칼 구현시 cycle 이 되는지 판단하는 부분에 대해 자세한 설명없이 코드를 구현했었는데 서로소 집합을 이용하여 구현하였습니다.
wiki site에서도 서로소 집합에 대한 부분을 언급하고 있습니다. 즉 cycle이 되는지 여부는 해당 노드가 같은 집합내에 있다면 cycle이 되는겁니다.
서로소 집합이란 두집합의 교집합이 공집합이 될때를 서로소라고 합니다.
즉 {1,2,3}, {4,5} 라고 한다면 교집합은 { } 가 되며 두 집합을 서로소라고 합니다.

어려운 내용은 아니나 집합에 대해 구현을 한번도 안해보았다면 언어로 구현하기 어렵게 느낄수 있는 내용입니다.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure 여기 site에 설명이 있습니다.

소개되는 내용은 3개의 함수로 구성됩니다.
집합을 만드는 함수, 집합을 합치기(집합에 원소를 추가), 집합의 이름 내지 대표자 찾기

Pseudocode로 나타내 보면 아래와 같다고합니다.
이걸 보고도 이해하기가 난해합니다.

 function MakeSet(x)
     x.parent := x

 function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

{1,2,3}, {4,5} 두개의 집합을 만들고 3은 어떤 집합에 있는지 4는 어떤 집합이 있는지 예제를 통해서 만들어 보겠습니다.
일단 구현을 하기전에 대표자"representative"라는 개념을 알아야 합니다.
집합에 속한 하나의 특정멤버를 통해 각 집합들을 구분하는데 이 특정멤버를 대표자라고 부릅니다.

아마도 이런식으로 표현해아 할겁니다.
MakeSet 각 원소를 개별로 집합을 만든다.
Union(1,2); // {1,2}
Union(1,3); // {1,2,3}
Union(5,4); // {5,4}
printf("%d\n",Find(3)); // 3이 속한 대표자의 값을 출력합니다.
printf("%d\n",Find(4)); // 4가 속한 대표자의 값을 출력합니다.



C, pasted 1 second ago: 

#include <stdio.h> #define MAX_N 100 int parent[MAX_N]; void MakeSet(int input) { parent[input]=input; } int Find(int input) { if(parent[input]==input) return input; return Find(parent[input]); } void Union(int input1,int input2) { int p1 = Find(input1); int p2 = Find(input2); parent[p1]=p2; } int main() { int i; for(i=1;i<=5;i++){ MakeSet(i); } Union(1,2); Union(1,3); Union(5,4); printf("%d\n",Find(1)); // 3이 속한 대표자의 값을 출력합니다. printf("%d\n",Find(5)); // 4가 속한 대표자의 값을 출력합니다. for(i=0;i<MAX_N;i++){ if(parent[i]!=0) printf("%d,parent %d\n",i,parent[i]); } return 0; }

Output:

3 4 1,parent 2 2,parent 3 3,parent 3 4,parent 4 5,parent 4

Find함수 호출시 부모 값을 이용해서 부모가 대표자가 아닌경우 다시 부모를 찾게된다. 대표자는 id와 부모가 같은 값이 됩니다. 여기에서는 {1,2,3} {4,5} 각각 3,4가 대표자가 됩니다.
1,parent 2
2,parent 3
3,parent 3
4,parent 4
5,parent 4