프림 알고리즘 문서 원본 보기

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

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

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

== 시간 복잡도 ==

{| class="wikitable"
! 최소 변 비용 자료 구조 !! 시간 복잡도 (총합)
|-
| [[인접 행렬]], 검색 || <math>V^2</math>
|-
| [[이진 힙]](아래 [[의사코드]]를 보라.) 및 [[인접 리스트]] || <math>O((V + E) log V) = E log V</math>
|-
| [[피보나치 힙]] 및 [[인접 리스트]] || <math>E + V \log V</math>
|}

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

== 예제 ==
{| class="wikitable" <!--border=1 cellspacing=0 cellpadding=5-->
! 그림 !! 설명 !! width="50" | 안 보임 !! width="80" | 경계 !! width="140" | 결과 집합
|-
|[[파일:Prim Algorithm 0.svg|200px]]
| 왼쪽에 있는 것이 우리가 문제를 풀어야 할 그래프이다. 왼쪽에 있는 그림은 트리가 아니다. [[트리 (그래프 이론)|트리]]의 정의에 의해 트리에는 [[순환 (그래프 이론)|순환]]이 없어야 하는데 왼쪽에 있는 그림에는 순환이 있기 때문이다. 왼쪽 도표의 정확한 이름은 그래프 또는 네트워크가 되겠다. 변 옆에 있는 숫자는 가중치를 나타낸다. 아직 아무 변도 색이 바뀌지 않았다. 임의의 점을 출발점으로 정할 수 있다. 꼭짓점 '''D'''를 출발점으로 정하겠다.
| C, G
| A, B, E, F
| D
|-
|[[파일:Prim Algorithm 1.svg|200px]]
| 다음으로는 '''D'''와 붙어 있는 꼭짓점을 선택해야 한다: '''A'''는 5만큼 떨어져있고(가중치가 5라는 뜻), '''B'''는 9 떨어져있고, '''E'''는 15 떨어져 있고, '''F'''는 6 떨어져 있다. 이 중 5가 가장 작으므로 꼭짓점 '''A''' 및 변 '''DA'''의 색을 바꾸겠다.
| C, G
| B, E, F
| A, D
|-
|[[파일:Prim Algorithm 2.svg|200px]]
| 다음 꼭짓점은 '''D''' 혹은 '''A'''와 붙어 있는 꼭짓점을 선택하면 된다. '''B'''는 '''D'''에서 9떨어져 있고, '''A'''에서 7 떨어져 있다. '''E'''는 '''D'''에서 15만큼 떨어져 있고, '''F'''는 6만큼 떨어져 있다. 6이 가장 작은 수이므로, '''F''' 및 '''DF'''의 색을 바꾸겠다.
| C
| B, E, G
| A, D, F
|-
|[[파일:Prim Algorithm 3.svg|200px]]
| 위와 같은 방법으로하면 '''A'''에서 7 떨어진 '''B'''가 선택된다. '''DB'''의 색을 빨강으로 바꾸겠다. '''B'''와 '''D'''가 이미 색이 바뀌어 있기 때문이다. 따라서 '''DB'''는 이용될 수 없다.
| 널
| C, E, G
| A, D, F, B
|-
|[[파일:Prim Algorithm 4.svg|200px]]
| 이 경우 우리는 '''C''', '''E''', 및 '''G''' 중 하나를 선택할 수 있다. '''C'''는 '''B'''에서 8 떨어져 있고, '''E'''는 '''B''에서 7 떨어져 있다. '''G'''는 '''F'''에서 11 떨어져 있다. '''E'''가 가장 가까우므로 '''E'''와 '''EB'''의 색을 바꾸겠다. 다른 두 개는 빨강으로 칠하겠는데, 이는 두 꼭짓점이 이미 사용되었기 때문이다.
| 널
| C, G
| A, D, F, B, E
|-
|[[파일:Prim Algorithm 5.svg|200px]]
| '''C'''와 '''G'''가 남아있다. '''C'''는 '''E'''에서 5떨어져 있고, '''G'''는 '''E'''에서 9 떨어져 있다. '''C'''를 선택하겠다. '''C'''와 '''EC'''의 색을 바꾸겠다. '''BC'''는 빨강으로 칠하겠다.
| 널
| G
| A, D, F, B, E, C
|-
|[[파일:Prim Algorithm 6.svg|200px]]
| '''G'''만 남아 있다. '''F'''에서 11 떨어져 있고, '''E'''에서 9 떨어져 있다. '''E'''가 가까우므로 '''EG'''의 색을 바꾸겠다. 이제 모든 꼭짓점의 색을 바꿨고, 최소 비용 [[신장트리]]가 녹색으로 표시되었다. 총 가중치 합은 39이다.
| 널
| 널
| A, D, F, B, E, C, G
|}

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

트리에 관한 정리에서 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]이다. <code>latest_addtion</code>이 된다.
: "경계"는 Q에 속한 v인데, "가장 가까운 꼭짓점"이 제거된 뒤 v와의 거리(distance) < ∞ 인 v이다.
: "안 보임"은 Q에 속한 v인데, "가장 가까운 꼭짓점"이 제거된 뒤 v와의 거리(distance) = ∞ 인 v이다.
최솟값 제거 함수가 [[널 문자|널]]을 반환하면 while 루프를 빠져나간다. [[인접 리스트]]를 설정해서 "방향이 있는 그래프"가 반환되게도 할 수는 있다.
: "시간 복잡도 : 루프에 대해서는 <math>V</math>, 제거 함수에 대해서는 <math>\log V</math>"
 '''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'')
: "시간 복잡도 : <math>E/V</math>, 꼭짓점 개수의 평균"
     '''for each''' ''adjacent'' '''of''' ''latest_addition''
     '''if''' (is_in_Q of ''adjacent'') and (weight-function(''latest_addition'', ''adjacent'') < min_distance of ''adjacent'')
         '''set''' parent '''of''' ''adjacent'' '''to''' ''latest_addition''
         '''set''' min_distance '''of''' ''adjacent'' '''to''' weight-function(''latest_addition'', ''adjacent'')
: "시간 복잡도 : <math>\log V</math>, 힙의 높이(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 [[Robert Tarjan|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. {{ISBN|0-262-03293-7}}. Section 23.2: The algorithms of Kruskal and Prim, pp.&nbsp;567–574.

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

== 외부 링크 ==
* {{위키공용분류-줄}}

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