개요

상호배타적인(교집합이 없는) 집합을 모델링
--> 집합 ADT의 특화

메소드

• set find(e) : 원소 e가 속한 집합 반환
• union(S1, S2) : 집합 S1, S2 합집합 수행
• int size(S) : 집합S의 크기(원소 개수) 반환

분리집합

배열로 구현된 리스트 기반

• 구성요소
  • 3개의 집합 A={0,1,4,5} B={2,6,8} C={3,7,9}가 있다고 가정
  • 크기 10의 일차원배열 V
• 구현
  • find 실행시간 O(1)
  • union 실행시간 O(n)

Alg init()
1. V[0], V[1], V[4], V[5] ← A
   V[2], V[6], V[8] ← B
   V[3], V[7], V[9] ← C
2. return

Alg find(e)    { 정수원소 e }
1. return V[e]

Alg Union(S1, S2)
1. for i ← 0 to 9
     if(V[i] = S2)
       V[i] ← S1
2. return

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 10

char find(char* V, int elem) {
	return V[elem]; 
}

void unionSet(char* V, char S1, char S2) { // S2를 S1에 통합
	for (int i = 0; i < N; i++) {
		if (V[i] == S2)
			V[i] = S1;
	}
}

void print(char* V) {
	printf("\n-------------------");
	printf("\nA : ");
	for (int i = 0; i < N; i++)
		if (V[i] == 'A') printf("%d ", i);
	printf("\nB : ");
	for (int i = 0; i < N; i++)
		if (V[i] == 'B') printf("%d ", i);
	printf("\nC : ");
	for (int i = 0; i < N; i++)
		if (V[i] == 'C') printf("%d ", i);
	printf("\n");
	printf("-------------------");
}

int main() {
	char V[N];
	V[0] = 'A'; V[1] = 'A'; V[4] = 'A'; V[5] = 'A';
	V[2] = 'B'; V[6] = 'B'; V[8] = 'B';
	V[3] = 'C'; V[7] = 'C'; V[9] = 'C';
	
	printf("%d is in %c\n", 0, find(V, 0));
	printf("%d is in %c\n", 7, find(V, 7));
	print(V);
	/*
	0 is in A
	7 is in C

	-------------------
	A : 0 1 4 5
	B : 2 6 8
	C : 3 7 9
	-------------------
	*/

	unionSet(V, 'A', 'B');
	print(V);
	/*
	-------------------
	A : 0 1 2 4 5 6 8
	B :
	C : 3 7 9
	-------------------
	*/
	return 0;
}

연결리스트로 구현된 리스트 기반

• 구성요소
  • N개의 분리집합이 있다고 가정
  • 각 분리집합을 나타내는 레코드 R
    • 필드 : size, head, tail
  • 레코드 R이 N개 있는 배열 V
  • N개의 연결리스트 S0, S1, S2, ... SN
    • 노드 프로퍼티 : elem, set, next
• 구현
  • union 상각실행시간 O( min(|S1|, |S2|) )

Alg init()
1. V ← empty array of Set Recodes
   for i ← 0 to N-1
     V[i] ← empty linked list
2. return

Alg node(e) : return node of element e
Alg setid(node) : return set identifier(name) of list

Alg find(e)
1. return setid(node(e).set).elem)

Alg union(S1, S2)		{ 작은 집합을 큰 집합에 병합 }
1. if(V[S1] ≥ V[S2])
     small ← S2
     big ← S1
   else
     small ← S1
     big ← S2
2. Hsmall ← V[small].head
   Tsmall ← V[small].tail
   Hbig ← V[big].head
   Tbig ← V[big].tail
3. p ← Hsmall			{ 큰집합 뒤에 작은집합 뒤에 붙이기 }
   while(p!=NULL)
     p.set ← Hbig
     p ← p.next
   Tbig.next ← Hsmall
4. V[big].tail ← Tsmall
   V[big].size ← V[S1].size + V[S2].size
5. V[small].head ← NULL		{ 작은집합 버리기 }
   V[small].tail ← NULL
   V[small].size ← 0
6. return

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct _Node {
	struct _Node* next;
	struct _Node* set;
	char elem;
} Node;

typedef struct _Record {
	int size;
	Node* head;
	Node* tail;
} Record;

int setidToIdx(char setid) {
	if (setid == 'X') return 0;
	else if (setid == 'Y') return 1;
	else if (setid == 'Z') return 2;
}

void addNode(Record* V, int setid, char elem) {
	int s = setidToIdx(setid);

	Node* p = (Node*)malloc(sizeof(Node));
	p->next = NULL;
	p->elem = elem;
	
	
	if (V[s].tail == NULL) {
		V[s].head = p;
		V[s].tail = p;
		p->set = p;
	}
	else {
		(V[s].tail)->next = p;
		V[s].tail = p;
		p->set = V[s].head;
	}

	V[s].size++;
}

void print(Record* V) {
	Node* p;
	
	for (int i = 0; i < 3; i++) {
		p = V[i].head;
		printf("[ %d ] ", i);
		while (p != NULL) {
			printf("%c ", p->elem);
			p = p->next;
		}
		printf("\n");
	}
}

Node* elemToNode(Record* V, char elem) { // elem값으로 노드 주소 획득
	Node* p;

	for (int i = 0; i < 3; i++) {
		p = V[i].head;
		while (p != NULL) {
			if (p->elem == elem)
				return p;
			p = p->next;
		}
	}
	return NULL;
}

char headElemToSetid(Record* V, char elem) {
	if (elem == (V[0].head)->elem) return 'X';
	else if (elem == (V[1].head)->elem) return 'Y';
	else if (elem == (V[2].head)->elem) return 'Z';
}

char find(Record* V, char elem) {
	Node* n = elemToNode(V, elem);
	return headElemToSetid(V, (n->set)->elem);
}

void unionSet(Record* V, char s1, char s2) { // 작은 집합을 큰 집합에 병합
	int idx1 = setidToIdx(s1);
	int idx2 = setidToIdx(s2);

	// 작은집합, 큰집합 결정
	int small, big;
	if (V[idx1].size >= V[idx2].size) {
		small = idx2;
		big = idx1;
	}
	else {
		small = idx1;
		big = idx2;
	}

	// 작은집합을 큰 집합 뒤에 붙이기
	Node* p = V[small].head;
	while (p != NULL) {
		p->set = V[big].head;
		p = p->next;
	}
	(V[big].tail)->next = V[small].head;
	V[big].tail = V[small].tail;
	V[big].size = V[big].size + V[small].size;

	// 기존 작은집합 비우기
	V[small].head = NULL;
	V[small].tail = NULL;
	V[small].size = 0;
}

int main() {
	Record V[3]; // 집합 X, Y, Z  (각 집합의 원소는 char)
	for (int i = 0; i < 3; i++) {
		V[i].size = 0;
		V[i].head = NULL;
		V[i].tail = NULL;
	}
	addNode(V, 'X', 'a'); addNode(V, 'X', 'b'); addNode(V, 'X', 'c'); addNode(V, 'X', 'd');
	addNode(V, 'Y', 'e'); addNode(V, 'Y', 'f'); addNode(V, 'Y', 'g');
	addNode(V, 'Z', 'h'); addNode(V, 'Z', 'i');
	print(V);

	// find
	printf("%c is in %c\n", 'a', find(V, 'a'));
	printf("%c is in %c\n", 'f', find(V, 'f'));
	printf("%c is in %c\n", 'h', find(V, 'h'));
	
	// union
	printf("\n");
	unionSet(V, 'Y', 'Z');
	print(V);

	printf("\n");
	unionSet(V, 'X', 'Y');
	print(V);

	return 0;
}

트리 기반

한 개 분리집합에 대해 한 개의 트리로 구현
루트노드로 집합식별자 구별

• 구성요소
  • 가상트리를 표현하는 크기 N의 1차원배열 parent

    인덱스는 노드의 값
    배열원소값은 부모노드의 값
    인덱스값 = 배열원소값 이면 루트노드

• 구현
  • find_1 시간복잡도 O(n) : 그냥 루트 찾아서 집합식별
  • union_1 시간복잡도 O(1) : 뒤 인수 집합을 앞 인수 집합에 병합
  • find_2 시간복잡도 O($log^*n$) <-- 거의 O(1) : 경로압축 적용
  • union_2 시간복잡도 O(1) : 작은집합을 큰 집합에 병합
  • find_3 시간복잡도 union_3과 함께 쓰면 O($log^*n$) : 부분 경로압축
  • union_3 시간복잡도 O($logn$) : 높이에 의한 합집합

Alg find_1(e)
1. if(parent[e]=e)
     return e
   else
     return find(parent[e])

Alg union_1(S1, S2)	{ S2를 S1의 부트리로 만들어 합집합 수행 }
1. parent[S2] ← S1
2. return

---

Alg find_2(e)
1. if(parent[e]=e)
     return e
   else		{ 경로압축 : 루트로 가는 경로 내 모든 노드의 부모포인터를 루트로 변경 }
     parent[e] ← find(parent[e])	
     return parent[e]
     
Alg union_2(S1, S2)
1. if(S1.size < S2.size)
     parent[S1] ← S2
     S2.size ← S1.size + S2.size
   else 
     parent[S2] ← S1
     S1.size ← S1.size + S2.size
2. return

---

Alg find_3(e)
1. p ← e
2. while(parent[p] != p)
     grandParent ← parent[parent[p]]
     if(grandParent != parent[p])
       parent[p] ← grandParent
     p ← parent[p]
3. return p

Alg union_3(S1, S2)
1. if(S1.height < S2.height)
     parent[S1] ← S2
   else
     parent[S2] ← S1
2. if (S1.height = S2.height)
     S1.height ← S1.height + 1
3. return

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 10

typedef struct _Tree {
	int size;
	int height;
	int root;
} Tree;

int parent[N] = { 0 };
Tree S1, S2;

void addNode(int par, int left, int right) {
	parent[left] = par;
	parent[right] = par;
}

void initParentArr() {
	for (int i = 0; i < N; i++)
		parent[i] = 0;
	
	S1.size = 3;
	S1.height = 1;
	S1.root = 1;
	parent[1] = 1; // root Set 1
	addNode(1, 2, 5);
	/*
		1
	  2	  5
	*/

	S2.size = 5;
	S2.height = 2;
	S2.root = 9;
	parent[9] = 9; // root Set 2
	addNode(9, 4, 6);
	addNode(4, 3, 7);
	/*
	        9
	   4         6
    3   7  
	*/
}

void printParentArr() {
	printf("\n---------------------\n");
	printf("index\t");
	for (int i = 0; i < N; i++)
		printf("%d ", i);
	printf("\n");

	printf("parent\t");
	for (int i = 0; i < N; i++)
		printf("%d ", parent[i]);
	printf("\n");
	printf("---------------------\n");
}

// -------------------

char find_1(int elem) {
	if (parent[elem] == elem)
		return elem;
	else
		find_1(parent[elem]);
	
}

char find_2(int elem) {
	if (parent[elem] == elem)
		return elem;
	else { // 경로압축
		parent[elem] = find_2(parent[elem]);
		return parent[elem];
	}
}

char find_3(int elem) {
	int p = elem;
	while (parent[p] != p) { // 부분적 경로압축
		int grandParent = parent[parent[p]];
		if (grandParent != parent[p])
			parent[p] = grandParent;
		p = parent[p];
	}

	return p;
}

// ----------

void union_1(Tree S1, Tree S2) { // S2를 S1에 병합
	parent[S2.root] = S1.root;
}

void union_2(Tree S1, Tree S2) {
	if (S1.size < S2.size) {
		parent[S1.root] = S2.root;
		S2.size += S1.size;
	}
	else {
		parent[S2.root] = S1.root;
		S1.size += S2.size;
	}
}

void union_3(Tree S1, Tree S2) {
	if (S1.height < S2.height) {
		parent[S1.root] = S2.root;
	}
	else {
		parent[S2.root] = S1.root;
	}

	if (S1.height == S2.height) {
		S1.height++;
	}
}

int main() {
	initParentArr();
	printParentArr();
	/*
	---------------------
	index   0 1 2 3 4 5 6 7 8 9
	parent  0 1 1 4 9 1 9 4 0 9
	---------------------
	*/

	union_1(S1, S2);
	printParentArr();

	initParentArr();
	union_2(S1, S2);
	printParentArr();

	initParentArr();
	union_3(S1, S2);
	printParentArr();
	/*
	---------------------
	index   0 1 2 3 4 5 6 7 8 9
	parent  0 1 1 4 9 1 9 4 0 1
	---------------------
	*/

	return 0;
}