프림 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

개요[편집]

프림 알고리즘은 아래의 순서대로 작동한다:

  1. 그래프에서 하나의 꼭짓점을 선택하여 나무를 만든다.
  2. 그래프의 모든 변이 들어 있는 집합을 만든다.
  3. 모든 꼭짓점이 나무에 포함되어 있지 않은 동안
    1. 나무와 연결된 변 가운데 나무 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 나무에 추가한다.

알고리즘이 종료됐을 때 만들어진 나무는 최소 비용 생성나무가 된다.

설명[편집]

이 알고리즘은 한 꼭짓점에서 시작한다. 나무가 모든 꼭짓점을 포함할 때까지 계속된다.

  • 입력: 연결된 각 변에 가중치가 주어진 그래프 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')가 결과가 된다. 이것은 최소 비용 생성나무가 된다.

시간 복잡도[편집]

최소 변 비용 자료 구조 시간 복잡도 (총합)
인접 행렬, 검색 V^2
이진 힙(아래 의사코드를 보라.) 및 인접 리스트 O((V + E) log V) = E log V
피보나치 힙인접 리스트 E + V \log V

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

예제[편집]

그림 설명 안 보임 경계 결과 집합
Prim Algorithm 0.svg 왼쪽에 있는 것이 우리가 문제를 풀어야 할 그래프이다. 왼쪽에 있는 그림은 나무가 아니다. 나무의 정의에 의해 나무에는 순환이 없어야 하는데 왼쪽에 있는 그림에는 순환이 있기 때문이다. 왼쪽 도표의 정확한 이름은 그래프 또는 네트워크가 되겠다. 변 옆에 있는 숫자는 가중치를 나타낸다. 아직 아무 변도 색이 바뀌지 않았다. 임의의 점을 출발점으로 정할 수 있다. 꼭짓점 D를 출발점으로 정하겠다. C, G A, B, E, F D
Prim Algorithm 1.svg 다음으로는 D와 붙어 있는 꼭짓점을 선택해야 한다: A는 5만큼 떨어져있고(가중치가 5라는 뜻), B는 9 떨어져있고, E는 15 떨어져 있고, F는 6 떨어져 있다. 이 중 5가 가장 작으므로 꼭짓점 A 및 변 DA의 색을 바꾸겠다. C, G B, E, F A, D
Prim Algorithm 2.svg 다음 꼭짓점은 D 혹은 A와 붙어 있는 꼭짓점을 선택하면 된다. BD에서 9떨어져 있고, A에서 7 떨어져 있다. ED에서 15만큼 떨어져 있고, F는 6만큼 떨어져 있다. 6이 가장 작은 수이므로, FDF의 색을 바꾸겠다. C B, E, G A, D, F
Prim Algorithm 3.svg 위와 같은 방법으로하면 A에서 7 떨어진 B가 선택된다. DB의 색을 빨강으로 바꾸겠다. BD가 이미 색이 바뀌어 있기 때문이다. 따라서 DB는 이용될 수 없다. C, E, G A, D, F, B
Prim Algorithm 4.svg 이 경우 우리는 C', E, 및 G 중 하나를 선택할 수 있다. C B에서 8 떨어져 있고, E B에서 7 떨어져 있다. GF에서 11 떨어져 있다. E가 가장 가까우므로 EEB의 색을 바꾸겠다. 다른 두 개는 빨강으로 칠하겠는데, 이는 두 꼭짓점이 이미 사용되었기 때문이다. C, G A, D, F, B, E
Prim Algorithm 5.svg CG가 남아있다. CE에서 5떨어져 있고, GE에서 9 떨어져 있다. C를 선택하겠다. CEC의 색을 바꾸겠다. BC는 빨강으로 칠하겠다. G A, D, F, B, E, C
Prim Algorithm 6.svg G만 남아 있다. F에서 11 떨어져 있고, E에서 9 떨어져 있다. E가 가까우므로 EG의 색을 바꾸겠다. 이제 모든 꼭짓점의 색을 바꿨고, 최소 비용 생성나무가 녹색으로 표시되었다. 총 가중치 합은 39이다. A, D, F, B, E, C, G

의사 코드[편집]

민-힙[편집]

초기화[편집]

입력
한 그래프, 변의 가중치를 반환하는 함수, 초기 꼭짓점.

처음에는 각 꼭짓점은 '아직 거치지 않은 꼭짓점들의 집합'(not yet seen set)에 속한다. 초기 꼭짓점을 정한다. 모든 꼭짓점들을 최소 힙에 두어서 최소 그래프의 최소 가중치를 기준으로 최소 힙에서 꼭짓점이 제거될 수 있게 해둔다.

for each vertex in graph
   set min_distance of vertex toset 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]이다. lastest_addtion이 된다.
"경계" 는 Q에 속한 v인데, "가장 가까운 꼭짓점"이 제거된 뒤 v와의 거리(distance) < ∞ 인 v이다.
"안 보임"은 Q에 속한 v인데, "가장 가까운 꼭짓점"이 제거된 뒤 v와의 거리(distance) = ∞ 인 v이다.

최솟값 제거 함수가 을 반환하면 와일(while) 루프를 빠져나간다. 인접 리스트를 설정해서 "방향이 있는 그래프"가 반환되게도 할 수는 있다.

"시간 복잡도 : 루프에 대해서는 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) < min_distance of adjacent)
        set parent of adjacent to latest_addition
        set min_distance of adjacent to 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. 57–63. (in Czech)
  • R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
  • D. Cherition and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal of Computing, 5 (Dec. 1976), pp. 724–741
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, 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. 567–574.

같이 보기[편집]

바깥 고리[편집]