프림 알고리즘

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

프림 알고리즘(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

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

예제[편집]

그림 설명 안 보임 경계 결과 집합
Prim Algorithm 0.svg 왼쪽에 있는 것이 우리가 문제를 풀어야 할 그래프이다. 왼쪽에 있는 그림은 트리가 아니다. 트리의 정의에 의해 트리에는 사이클이 없어야 하는데 왼쪽에 있는 그림에는 사이클이 있기 때문이다. 왼쪽 도표의 정확한 이름은 그래프 혹은 네트워크가 되겠다. 변(arc) 옆에 있는 숫자는 무게(weight), 다른 말로 비용(cost)을 나타낸다. 아직 아무 변도 색이 바뀌지 않았다. 임의의 점을 출발점으로 정할 수 있다. 정점 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의 색을 바꾸겠다. 이제 모든 정점의 색을 바꿨고, 최소 비용 신장 트리가 녹색으로 표시되었다. 총 비용(cost or weight) 합은 39이다. A, D, F, B, E, C, G

의사 코드[편집]

민-힙[편집]

초기화[편집]

입력
한 그래프, 에지 웨이트(edge weight)를 반환하는 펑션, 초기 정점.

처음에는 각 정점은 '아직 안 보이는 정점들의 집합'(not yet seen set)에 속한다. 초기 정점(initial vertex)를 정한다. 모든 정점들을 민-힙에 두어서 미니멈 그래프의 최소 웨이트를 기준으로 민-힙에서 정점이 제거될 수 있게 해둔다.

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.

같이 보기[편집]

바깥 고리[편집]