프림 알고리즘

**프림 알고리즘**(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 <math>{\color{Blue}O}(E \log V)</math>의 시간복잡도를 가진다. 그래프가 충분히 빽빽한 경우(<math>E = {\color{Blue}\Omega}(V \log V)</math>)에는 피보나치 힙을 이용하여 훨씬 빠르게 할 수 있다. 이 방법은 복잡도가 <math>{\color{Blue}O}(E + V \log V)</math>까지 떨어진다.

## 개요
프림 알고리즘은 아래의 순서대로 작동한다:
# 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다.
# 그래프의 모든 변이 들어 있는 집합을 만든다.
# 모든 꼭짓점이 트리에 포함되어 있지 않은 동안
## 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.
알고리즘이 종료됐을 때 만들어진 트리는 최소 비용 신장트리가 된다.

## 설명
이 알고리즘은 한 꼭짓점에서 시작한다. 트리가 모든 꼭짓점을 포함할 때까지 계속된다.
* 입력: 연결된 각 변에 가중치가 주어진 그래프 G(V,E)
* 초기화: V' = {x}로 놓는다. x는 V에 있는 임의의 꼭짓점이다. E'= \{\}로 놓는다.
* V'=V 가 될 때까지 다음을 계속 수행한다:
** E로부터 최소의 가중치를 갖는 변 (u,v)를 뽑아낸다. 단, 이때 u는 V'에 속해야 하고 v는 V'에 속하지 말아야 한다. (같은 가중치를 갖는 여러 개의 변이 존재할 경우에는, 임의의 것을 고른다.)
** v를 V'에 추가한다.(u,v)를 E'에 추가한다.
* 결과: 알고리즘이 종료됐을 때 만들어진 트리 G(V',E')가 결과가 된다. 이것은 최소 비용 신장트리가 된다.

## 시간 복잡도

인접 행렬과 최소 비용값들이 들어가 있는 배열 내에서 최소 비용값을 찾는 검색을 사용할 경우, 시간 복잡도는 <math>{\color{Blue}O}(V^2)</math>가 된다. 이진 힙 자료 구조와 인접 리스트 표현을 사용한다면, 프림 알고리즘은 <math>{\color{Blue}O}(E \log V)</math> 내에 수행된다는 것이 증명될 수 있다. 여기서 E는 변의 개수이고, V는 꼭짓점의 개수이다. 약간 복잡한 자료 구조인 피보나치 힙을 사용한다면 O(E + V \log V)로 시간 복잡도가 감소할 수 있다. 이 경우, 그래프가 조밀하여 E가 \Omega(V \log V)일 땐, 상당히 빨라진다.

## 예제

## 정확성 증명
프림 알고리즘으로 얻은 그래프가 신장트리임을 보이는 것과 최소비용임을 보이는 두 단계로 나눈다.

트리에 관한 정리에서 n개의 꼭짓점을 가진 연결된 그래프가 n-1개의 변을 가지면 트리라고 한다. 프림 알고리즘으로 얻은 그래프 P는 n개의 꼭짓점을 연결하고 있고 n-1개의 변을 가지므로 트리이며 모든 점 n개를 가지므로 신장트리이다.

P가 최소비용임은 수학적 강귀납법을 통해 다음 명제를 증명하여 보인다.

"프림 알고리즘 각 단계에서 얻는 그래프의 간선들을 원소로하는 집합을 포함한 최소비용 신장트리가 항상 존재한다"
# 프림 알고리즘 첫 단계는 간선이 없다. 그러므로 간선들의 집합은 공집합이다. 그러므로 최소비용 신장트리가 무엇이든 간선들의 집합을 포함한다.
# 프림 알고리즘의 1부터 n-2 단계까지에서 얻는 그래프의 간선들을 원소로하는 집합을 포함한 최소비용 신장트리가 존재한다고 가정하자.
# n-2 단계로 얻는 그래프는 Q이고 간선들의 집합 L을 포함하는 최소비용 신장트리를 T라고 하자. Q에서 아직 연결되지 않은 마지막 꼭짓점 E를 한점으로 하는 변 e를 그리면 P를 얻는다. 그러므로 P와 T는 L을 공통으로 포함하고 E를 연결하는 변만 차이가 있다. 이때 T는 최소비용 신장트리이고 P도 가중치가 가장 낮은 e를 그려서 얻으므로 T와 P는 비용이 동일하다. 그러므로 n-1 단계에서 얻는 그래프 P의 간선 집합을 포함하는 최소비용 신장트리 P 자신이 존재한다.

## 의사 코드

### 최소-힙(Min-Heap)

#### 초기화
;입력: 한 그래프, 변의 가중치를 반환하는 함수, 초기 꼭짓점.
처음에는 각 꼭짓점은 '아직 거치지 않은 꼭짓점들의 집합'(not yet seen set)에 속한다. 초기 꼭짓점을 정한다. 모든 꼭짓점들을 최소 힙에 두어서 최소 그래프의 최소 가중치를 기준으로 최소 힙에서 꼭짓점이 제거될 수 있게 해둔다.
 **for each** *vertex* **in** *graph*
    **set** min_distance **of** *vertex* **to** ∞
    **set** parent **of** *vertex* **to** *null*
    **set** minimum_adjacency_list **of** *vertex* **to** empty list
    **set** is_in_Q **of** *vertex* **to** true
 **set** distance **of** initial vertex **to** *zero*
 add to minimum-heap **Q** all vertices in graph.

#### 용어 설명
: "가장 가까운 꼭짓점" 은 Q[0]이다. `latest_addtion`이 된다.
: "경계"는 Q에 속한 v인데, "가장 가까운 꼭짓점"이 제거된 뒤 v와의 거리(distance) V, 제거 함수에 대해서는 \log V"
 **while** *latest_addition* = remove minimum in **Q**
     **set** is_in_Q **of** *latest_addition* to false
     add *latest_addition* to (minimum_adjacency_list of (parent of *latest_addition*))
     add (parent of *latest_addition*) to (minimum_adjacency_list of *latest_addition*)
: "시간 복잡도 : E/V, 꼭짓점 개수의 평균"
     **for each** *adjacent* **of** *latest_addition*
     **if** (is_in_Q of *adjacent*) and (weight-function(*latest_addition*, *adjacent*) \log V, 힙의 높이(height of heap)"
         update *adjacent* in **Q**, order by min_distance

## 참고 문헌
* V. Jarník: *O jistém problému minimálním* [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp.&nbsp;57–63. (in Czech)
* R. C. Prim: *Shortest connection networks and some generalisations*. In: *Bell System Technical Journal*, 36 (1957), pp.&nbsp;1389–1401
* D. Cherition and R. E. Tarjan: *Finding minimum spanning trees*. In: *SIAM Journal of Computing*, 5 (Dec. 1976), pp.&nbsp;724–741
* Thomas H. Cormen, Charles E. Leiserson, 로널드 라이베스트, and Clifford Stein. *[[Introduction to Algorithms]]*, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 23.2: The algorithms of Kruskal and Prim, pp.&nbsp;567–574.

## 같이 보기
* 신장트리
* 크루스칼 알고리즘

## 외부 링크
* 

분류:트리 구조
분류:그래프 알고리즘
분류:에츠허르 데이크스트라