'''프림 알고리즘'''(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 시간복잡도를 가진다. 그래프가 충분히 빽빽한 경우()에는 피보나치 힙을 이용하여 훨씬 빠르게 있다. 방법은 복잡도가 까지 떨어진다. == 개요 == 프림 알고리즘은 아래의 순서대로 작동한다: 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다. 그래프의 모든 변이 들어 있는 집합을 만든다. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안 ## 트리와 연결된 가운데 트리 속의 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다. 알고리즘이 종료됐을 만들어진 트리는 최소 비용 신장트리가 된다. == 설명 == 알고리즘은 꼭짓점에서 시작한다. 트리가 모든 꼭짓점을 포함할 때까지 계속된다. 입력: 연결된 변에 가중치가 주어진 그래프 초기화: 놓는다. x는 V에 있는 임의의 꼭짓점이다. 놓는다. 때까지 다음을 계속 수행한다: ** 로부터 최소의 가중치를 갖는 (u,v)를 뽑아낸다. 단, 이때 u는 속해야 하고 v는 속하지 말아야 한다. (같은 가중치를 갖는 여러 개의 변이 존재할 경우에는, 임의의 것을 고른다.) ** v를 추가한다.(u,v)를 추가한다. 결과: 알고리즘이 종료됐을 만들어진 트리 결과가 된다. 이것은 최소 비용 신장트리가 된다. == 시간 복잡도 == 최소 비용 자료 구조 시간 복잡도 (총합) 인접 행렬, 검색 이진 힙(아래 의사코드를 보라.) 인접 리스트 피보나치 인접 리스트 인접 행렬과 최소 비용값들이 들어가 있는 배열 내에서 최소 비용값을 찾는 검색을 사용할 경우, 시간 복잡도는 된다. 이진 자료 구조와 인접 리스트 표현을 사용한다면, 프림 알고리즘은 내에 수행된다는 것이 증명될 있다. 여기서 변의 개수이고, 꼭짓점의 개수이다. 약간 복잡한 자료 구조인 피보나치 힙을 사용한다면 시간 복잡도가 감소할 있다. 경우, 그래프가 조밀하여 땐, 상당히 빨라진다. == 예제 == 그림 설명 보임 경계 결과 집합 200px 왼쪽에 있는 것이 우리가 문제를 풀어야 그래프이다. 왼쪽에 있는 그림은 트리가 아니다. 트리의 정의에 의해 트리에는 순환이 없어야 하는데 왼쪽에 있는 그림에는 순환이 있기 때문이다. 왼쪽 도표의 정확한 이름은 그래프 또는 네트워크가 되겠다. 옆에 있는 숫자는 가중치를 나타낸다. 아직 아무 변도 색이 바뀌지 않았다. 임의의 점을 출발점으로 정할 있다. 꼭짓점 '''D'''를 출발점으로 정하겠다. C, A, B, E, 200px 다음으로는 '''D'''와 붙어 있는 꼭짓점을 선택해야 한다: '''A'''는 5만큼 떨어져있고(가중치가 5라는 뜻), '''B'''는 떨어져있고, '''E'''는 15 떨어져 있고, '''F'''는 떨어져 있다. 5가 가장 작으므로 꼭짓점 '''A''' '''DA'''의 색을 바꾸겠다. C, B, E, A, 200px 다음 꼭짓점은 '''D''' '''혹은''' '''A'''와 붙어 있는 꼭짓점을 선택하면 된다. '''B'''는 '''D'''에서 9떨어져 있고, '''A'''에서 떨어져 있다. '''E'''는 '''D'''에서 15만큼 떨어져 있고, '''F'''는 6만큼 떨어져 있다. 6이 가장 작은 수이므로, '''F''' '''DF'''의 색을 바꾸겠다. B, E, A, D, 200px 위와 같은 방법으로하면 '''A'''에서 떨어진 '''B'''가 선택된다. '''DB'''의 색을 빨강으로 바꾸겠다. '''B'''와 '''D'''가 이미 색이 바뀌어 있기 때문이다. 따라서 '''DB'''는 이용될 없다. C, E, A, D, F, 200px 경우 우리는 '''C''', '''E''', '''G''' 하나를 선택할 있다. '''C'''는 '''B'''에서 떨어져 있고, '''E'''는 '''B''에서 떨어져 있다. '''G'''는 '''F'''에서 11 떨어져 있다. '''E'''가 가장 가까우므로 '''E'''와 '''EB'''의 색을 바꾸겠다. 다른 개는 빨강으로 칠하겠는데, 이는 꼭짓점이 이미 사용되었기 때문이다. C, A, D, F, B, 200px '''C'''와 '''G'''가 남아있다. '''C'''는 '''E'''에서 5떨어져 있고, '''G'''는 '''E'''에서 떨어져 있다. '''C'''를 선택하겠다. '''C'''와 '''EC'''의 색을 바꾸겠다. '''BC'''는 빨강으로 칠하겠다. A, D, F, B, E, 200px '''G'''만 남아 있다. '''F'''에서 11 떨어져 있고, '''E'''에서 떨어져 있다. '''E'''가 가까우므로 '''EG'''의 색을 바꾸겠다. 이제 모든 꼭짓점의 색을 바꿨고, 최소 비용 신장트리가 녹색으로 표시되었다. 가중치 합은 39이다. A, D, F, B, E, C, == 정확성 증명 == 프림 알고리즘으로 얻은 그래프가 신장트리임을 보이는 것과 최소비용임을 보이는 단계로 나눈다. 트리에 관한 정리에서 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의 간선 집합을 포함하는 최소비용 신장트리 자신이 존재한다. == 의사 코드 == === 최소-힙(Min-Heap) === ==== 초기화 ==== ;입력: 그래프, 변의 가중치를 반환하는 함수, 초기 꼭짓점. 처음에는 꼭짓점은 '아직 거치지 않은 꼭짓점들의 집합'(not yet seen set)에 속한다. 초기 꼭짓점을 정한다. 모든 꼭짓점들을 최소 힙에 두어서 최소 그래프의 최소 가중치를 기준으로 최소 힙에서 꼭짓점이 제거될 있게 해둔다. '''for each''' ''vertex'' '''in''' ''graph'' '''set''' min_distance '''of''' ''vertex'' '''to''' '''set''' parent '''of''' ''vertex'' '''to''' ''null'' '''set''' '''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. ==== 용어 설명 ==== "가장 가까운 꼭짓점" Q0이다. latest_addtion이 된다. "경계"는 Q에 속한 v인데, "가장 가까운 꼭짓점"이 제거된 v와의 거리(distance) v이다. "안 보임"은 Q에 속한 v인데, "가장 가까운 꼭짓점"이 제거된 v와의 거리(distance) v이다. 최솟값 제거 함수가 널을 반환하면 while 루프를 빠져나간다. 인접 리스트를 설정해서 "방향이 있는 그래프"가 반환되게도 수는 있다. "시간 복잡도 루프에 대해서는 제거 함수에 대해서는 '''while''' remove minimum in '''Q''' '''set''' is_in_Q '''of''' to false add to of (parent of add (parent of to of "시간 복잡도 꼭짓점 개수의 평균" '''for each''' ''adjacent'' '''of''' '''if''' (is_in_Q of ''adjacent'') and ''adjacent'') min_distance of ''adjacent'') '''set''' parent '''of''' ''adjacent'' '''to''' '''set''' min_distance '''of''' ''adjacent'' '''to''' ''adjacent'') "시간 복잡도 힙의 높이(height of heap)" update ''adjacent'' in '''Q''', order by min_distance == 참고 문헌 == V. Jarník: ''O jistém problému minimálním'' About 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 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'', (Dec. 1976), pp. 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. 567–574. == 같이 보기 == 신장트리 크루스칼 알고리즘 == 외부 링크 == 분류:트리 구조 분류:그래프 알고리즘 분류:에츠허르 데이크스트라