프림 알고리즘

프림 알고리즘 (Prim's algorithm) 은 가중치가 있는 연결 무방향 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 탐욕적인 알고리즘입니다. 즉, 그래프의 모든 정점을 포함하면서 간선 가중치의 합이 최소가 되는 트리 구조를 찾는 알고리즘입니다.

개요

프림 알고리즘은 다음과 같은 단계로 진행됩니다.

1. 시작 정점 선택: 그래프 내의 임의의 정점을 시작 정점으로 선택합니다. 이 정점을 MST 집합에 추가합니다.
2. 최소 비용 간선 선택: MST 집합에 있는 정점과 MST 집합에 없는 정점을 연결하는 간선 중에서 가중치가 가장 작은 간선을 선택합니다.
3. 정점 추가: 선택된 간선으로 연결된 정점을 MST 집합에 추가합니다.
4. 반복: MST 집합에 그래프의 모든 정점이 포함될 때까지 2단계와 3단계를 반복합니다.

특징

• 탐욕적 접근: 매 단계마다 가장 작은 가중치를 가진 간선을 선택하는 방식으로 최적해를 찾아갑니다.
• 정점 중심: 크루스칼 알고리즘이 간선 중심으로 동작하는 것과 달리, 프림 알고리즘은 정점을 중심으로 확장해 나갑니다.
• 구현: 우선순위 큐(Priority Queue)를 사용하여 효율적으로 구현할 수 있습니다. 우선순위 큐는 MST 집합에 있는 정점과 MST 집합에 없는 정점을 연결하는 간선들의 가중치를 저장하고, 가장 작은 가중치를 가진 간선을 빠르게 찾을 수 있도록 합니다.

시간 복잡도

프림 알고리즘의 시간 복잡도는 구현 방식에 따라 달라집니다.

• 인접 행렬 사용: O(V^2) (V는 정점의 개수)
• 이진 힙 (Binary Heap) 사용: O(E log V) (E는 간선의 개수, V는 정점의 개수)
• 피보나치 힙 (Fibonacci Heap) 사용: O(E + V log V)

활용

프림 알고리즘은 네트워크 설계, 도로 건설, 통신망 구축 등 다양한 분야에서 활용될 수 있습니다. 예를 들어, 도시들을 연결하는 도로망을 건설할 때 총 도로의 길이를 최소화하는 경로를 찾거나, 컴퓨터 네트워크에서 모든 컴퓨터를 연결하면서 통신 비용을 최소화하는 네트워크를 구축하는 데 사용될 수 있습니다.