프림 알고리즘 (Prim's Algorithm)

Minimum Spanning Tree 문제를 해결하기 위해서 보통 두 가지 종류의 알고리즘 중 하나를 선택하여 사용한다.

 

1. 프림 알고리즘 (Prim's Algorithm)
2. 크루스칼 알고리즘 (Kruskal's Algorithm)

 

이 두 가지 알고리즘 모두 MST 문제에서 최적의 값을 도출할 수 있음이 이미 증명되어 있다.

 

이번에는 프림 알고리즘에 대하여 알아보도록 하겠다.

 

프림 알고리즘의 핵심은, 현재 우리가 가지고 있는 MST와 Edge 하나로 직접적으로 연결된 Vertex 가운데 Weight가 가장 작은 것을 추가한다는 것이다.

 

모든 Edge를 확인했는데 V-1개의 Edge가 선택되지 않은 경우가 있다면 그래프가 Disconnected 되어있다는 뜻이다.

 

 

이미 MST에 포함된 Vertex에서부터 V_k+1까지 최소 가중치의 경로로 가기 위해서 E_k라는 Edge를 선택해야 한다.

 

여기에서, E_k를 선택하지 않았을 때 더 좋은 결과를 얻을 수 있을 것이라고 가정해보자.

그렇다면, 위의 그림과 같은 결과가 나타난다. 왜냐하면, 신장 트리는 결국 모드를 포함해야 하므로, 결국 E_k가 아닌 다른 경로를 통해 V_k+1을 MST에 연결하게 된다. MST는 기존의 가중치보다 더 높은 가중치를 가지게 된다. 따라서, 가정이 틀렸다는 것이 증명되었다.

 

프림 알고리즘의 시간 복잡도에 대해 알아보도록 하자.

프림 알고리즘의 시간 복잡도는 어떤 자료구조를 사용하는지에 따라 달라진다.

우선순위 큐를 사용하는 경우와 배열을 사용하는 경우 두 가지 경우를 보겠다.

 

우선순위 큐

- 모든 노드에 대해 탐색하는 비용 : O(V)

- 우선순위 큐를 사용하여 최소 간선을 찾는 시간 : O(logV)

- 따라서 탐색 과정에는 O(VlogV)가 소요된다.

- 각 노드의 인접 간선을 찾는 시간은 모든 노드의 차수와 동일

- 각 간선에 대해 힙에 넣는 과정 : O(logV)

- 우선순위 큐 구성 : O(ElogV)

- 따라서 O(VlogV + ElogV)로 O(ElogV)가 된다.

 

배열

- 각 정점에 최소 간선을 갖는 정점 탐색을 매 정점마다 수행하므로 O(|V|²)

- 탐색 결과를 기반으로 각 정점의 최소 비용 연결 정점 탐색에는 O(1)이 소요

- 따라서 O(|V|²)

 

*해당 게시글은 K-Mooc 허재필 교수님의 강의 <인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고>의 강의 내용을 참고하여 작성되었음을 알립니다.