23. Disjoint Set 분리집합 자료구조 및 알고리즘 C/C++

1. 개요

 분리집합(Disjoint Set) 자료구조란 집합에 관한 3개의 연산에 관한 자료구조.

 무척 쉬움.

 최소신장트리(MST)를 구성하는 크루스칼 알고리즘을 작성하기위해 사용.(이외에도 많은 알고리즘에서 사용)

 크루스칼 알고리즘에 그래프의 Cycle Check를 위한 2가지 방식 존재, Disjoint Set과 DFS 방식.

 여기서 보통 가장 최선의 방법은 Disjoint Set이며 다른 알고리즘에도 많이 사용되므로 이를 위해 정리.

 Disjoint Set 자료구조

 struct DisjointSet{

     struct DisjointSet* parent;

int data;

int rank; //트리의 균형을 잡기위한 Factor

 };

 3개의 연산

 (1) MakeSet( ) // Disjoint Set 자료구조 생성, 메모리 할당 및 초기화(노드 생성 과정과 다를것 없음)

 (2) FIND( ) // 파라메터로 들어온 집합의 최상위 부모 노드 반환

 (3) UNION( ) // 파라메터 들어온 두 분리집합을 하나의 집합으로 합침

 *그래프의 Cycle을 측정하는 방법*

 (1) 두 분리집합의 FIND( ) 연산의 결과가 같으면 이미 두 집합은 연결되어 있다는 의미.(즉, 또 연결하면 Cycle)

 (2) 두 분리집합의 FIND( ) 연산의 결과가 다르면 두 집합은 아직 만나지 않는다는 의미.(즉, 비연결 상태)

 유투브 강의: https://www.youtube.com/watch?v=ID00PMy0-vE

2. 문제

 분리집합의 자료구조와 각 연산을 설계하시오.

3. 출력

3-1) 구조체 및 함수 선언

3-2) 메인

3-3) MakeSet( )

3-4) UNION( )

3-5) FIND( )

3-6) 출력

4. 핵심

 기억해야 할 것

 (1) 그래프 이론에서 Disjoint Set의 연산은 많이 사용되므로 꼭 알아둘 것

 (2) 모든 기준은 각 노드의 최상위의 노드랑 연관이 생김