22. 최소신장트리(MST) 프림(Prim) 알고리즘

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)