07-06 분리 집합(Disjoint Set)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

 

1.분리집합(Disjoint Set)

 1)정의

 -서로 공통된 원소를 갖지 않는(교집합이 없는 상태) 복수의 집합.

 -분리 집합은 합집합만이 존재할 수 있다.

 -분리 집합은 집합 간의 교집합이 존재하기 않기 때문에 소속관계가 분명해야하는 데이터를 다룰 때 유용하다.

2.분리집합 표현

 1)개요

 -트리와 이진트리는 부모가 자식을 가리키는 링크 또는 주소를 가지고 있고 분리집합은

 반대로 자식이 부모를 가리킨다.

 -뿌리 노드는 집합 그 자체이고, 뿌리 노드는 자신을 포함한 트리 내의 모든 노드는 그

  집합에 소속된다.

 -분리 집합 기본연산에는 두 집합을 합치는 합집합(Union) 연산과 원소가 속한 집합을 찾는 연산이 있다.

 

 

 

3.분리 집합 구현

 1)데이터 노드 구현

 

 

 2)함수 원형 선언

 3)함수 구현

  -합집합 연산

   한 쪽의 집합을 다른 쪽의 자식 노드로 만든다.

  

 

 -집합 탐색 연산

-노드 생성 및 소멸 연산

-테스트