Simple in Complex with Simple

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) 모든 기준은 각 노드의 최상위의 노드랑 연관이 생김

1. 개요

 프림 알고리즘은 아주 간단함.

 프림 알고리즘은 최소 신장 트리(MST)를 만드는데에 사용.

 신장 트리(ST)란 사이클을 형성하지 않지만 모든 노드가 간선(Edge)로 연결되어 있는 그래프.

 최소 신장 트리(MST)란 사이클을 형성하지 않으면서 모든 간선(Edge)가 최소로 연결된 그래프.

 신장 트리의 노드가 N개면 엣지의 개수는 N-1개 필요.

 다익스트라 알고리즘과 굉장히 유사함. 하지만 더 쉬움.

 무방향 그래프이기 때문에 어느 정점에서 시작하든 결국 결과는 같음. (동등한 거리로 인해 경로는 다를 수 있음)

 MST의 사용처는 전국을 연결하는 네트워크 및 고속도로 설계 또는 전자회로의 최소 선 길이 등등 사용.

 다른 알고리즘으로는 크루스칼(Kruskal) 알고리즘 존재.

 크루스칼 알고리즘과의 차이는 챕터 24에서 정리.

 알고리즘

 (1) 우선순위 큐에 시작 노드를 넣는다.

 (2) 우선순위 큐가 비어있지 않다면 노드를 꺼낸다.

 (3) 꺼낸 노드가 이미 방문한 노드라면 (2)로 넘어간다.

 (4) 방문하지 않는 노드라면 현재 경로와 거리 방문 배열을 처리한다.

 (5) 이 노드와 연결된 모든 노드를 우선순위 큐에 넣는다.

 (6) (2)를 우선순위 큐가 비어있을 때까지 반복한다. 

2. 문제

문제 출처: https://www.youtube.com/watch?v=3fU0w9XZjAA

 다음 그래프의 MST를 완성하는 프림 알고리즘을 작성하시오.

3. 출력

3-1) 구조체, 전역 변수, 함수 선언

3-2) 메인

3-3) 프림(prim) 알고리즘

3-4) 0(a)에서 시작한 출력

3-5) 8(i)에서 시작한 출력

4. 해설

 이번 코드는 스승님이 처음으로 배신한 알고리즘이다. 그렇기에 스승님 코드를 수정하느라 엄청난 시간을 허비했다.

그래도 3일간 헤매면서 프림 알고리즘에 대해 빠삭하게 알게되었다. 유익한 시간이었다.

 기억해야할 것

(1) 우선순위 큐를 사용할 것(가장 좋은것은 fibo heap이라지만 fibo heap이 무엇인지 몰라서 일단은 min heap사용)

 (2) 프림 알고리즘은 밀집 그래프와 노드 수보다 엣지 수가 많을수록 좋다. 

 (3) min heap일 경우 O(ElogV), fibo heap일 경우 O(E+VlogV)