프림 알고리즘

Prim's algorithm
유클리드 거리에 기초한 프림의 알고리즘 데모

컴퓨터 과학에서 프림의 알고리즘(Jarnik's algorithm)은 가중치 무방향 그래프에 대한 최소 스패닝 트리를 찾는 탐욕 알고리즘이다.즉, 모든 정점을 포함하는 트리를 형성하는 가장자리 서브셋을 찾습니다. 여기서 트리의 모든 모서리의 총 무게가 최소화됩니다.알고리즘은 임의의 시작 정점에서 이 트리를 한 번에 한 정점씩 구축하여 트리에서 다른 정점으로 가능한 한 저렴한 연결을 추가하는 방식으로 작동합니다.

이 알고리즘은 체코의 수학자 Vojtchch Jarnik에[1] 의해 1930년에 개발되었고 나중에 컴퓨터 과학자인 Robert C에 의해 재발견되고 재발행되었다. 1957년[2] 프라임, 1959년 [3]에드거 W. 다이크스트라.따라서 Jarnik'[4]s 알고리즘, Prim-Jarnik 알고리즘,[5] Prim-Dijkstra 알고리즘[6] 또는 DJP [7]알고리즘이라고도 합니다.

이 문제의 다른 잘 알려진 알고리즘으로는 Kruskal의 알고리즘과 Borkavka의 [8]알고리즘이 있습니다.이러한 알고리즘은 연결이 끊긴 그래프에서 최소 스패닝 포레스트를 찾습니다. 대조적으로 Prim 알고리즘의 가장 기본적인 형식은 연결된 그래프에서 최소 스패닝 트리만 찾습니다.그러나 Prim의 알고리즘을 그래프의 연결된 각 컴포넌트에 대해 개별적으로 실행하면 최소 스패닝 [9]포리스트를 찾는 데도 사용할 수 있습니다.점근 시간 복잡도 측면에서, 이 세 가지 알고리즘은 희박한 그래프에 대해 동일하게 빠르지만 더 정교한 [7][6]다른 알고리즘보다 느리다.그러나 충분히 조밀한 그래프의 경우 Prim의 알고리즘을 선형 시간으로 실행하여 다른 [10]알고리즘의 시간 범위를 충족하거나 개선할 수 있습니다.

프림의 알고리즘은 정점 A에서 시작합니다.3단계에서는 엣지 BD와 AB가 모두 무게 2를 가지므로 임의로 BD를 선택한다.이 단계가 끝나면 AB는 트리에 이미 있는 두 개의 노드를 연결하기 때문에 트리에 추가할 수 없습니다.

묘사

알고리즘은 비공식적으로 다음 단계를 수행하는 것으로 설명될 수 있습니다.

  1. 그래프에서 임의로 선택한 단일 정점으로 트리를 초기화합니다.
  2. 트리를 트리에 없는 정점에 연결하는 가장자리 중 트리를 한 가장자리만큼 키우고 최소 무게 가장자리를 찾아 트리로 전송합니다.
  3. 순서 2를 반복합니다(모든 정점이 트리에 있을 때까지).

상세한 것에 대하여는, 다음의 의사 코드에 따라서 실장할 수 있습니다.

  1. 그래프의 각 정점 v에 숫자 C[v](v에 대한 가장 저렴한 연결 비용)와 에지 E[v](가장 저렴한 연결을 제공하는 에지)를 연관시킵니다.이러한 값을 초기화하려면 C[v]의 모든 값을 +µ(또는 최대 에지 가중치보다 큰 수치)로 설정하고 각 E[v]를 이전 정점에 v를 연결하는 에지가 없음을 나타내는 특수 플래그 값으로 설정합니다.
  2. 빈 포레스트 F와 아직 F에 포함되지 않은 정점 집합 Q를 초기화합니다(처음에는 모든 정점).
  3. Q가 비워질 때까지 다음 단계를 반복합니다.
    1. 가능한 최소값 C[v]를 갖는 꼭지점 v를 Q에서 찾아 제거합니다.
    2. F에 v 추가
    3. v를 다른 꼭지점 w에 연결하는 가장자리 vw 위로 루프합니다.w가 여전히 Q에 속해 있고 vw의 무게가 C[w]보다 작을 경우 각 엣지에 대해 다음 절차를 수행합니다.
      1. C[w]를 엣지 vw 비용으로 설정
      2. E[w]를 엣지 vw를 가리키도록 설정합니다.
  4. 반환 F

위에서 설명한 바와 같이 알고리즘의 시작 정점은 임의로 선택됩니다.알고리즘의 메인 루프의 첫 번째 반복은 모두 동일한 가중치를 갖는 Q의 정점 세트를 가지며 알고리즘은 입력 그래프의 각 연결된 구성요소의 스패닝 트리를 완성할 때 자동으로 F의 새로운 트리를 시작합니다.알고리즘은 C[s]를 C의 다른 값보다 작은 수치(예를 들어 0)로 설정함으로써 특정 정점s로 시작하도록 변경할 수 있습니다.또, 다른 vert와 마주칠 때마다, 스패닝 포레스트 전체가 아닌, 1개의 스패닝 트리만을 찾도록 변경할 수도 있습니다(비공식적인 설명과 보다 밀접하게 일치).연관된 엣지가 없는 것으로 플래그 지정되었습니다.

알고리즘의 다양한 변형은 집합 Q가 구현되는 방식에서 서로 다릅니다. 즉, 단순한 링크 리스트 또는 정점 배열 또는 보다 복잡한 우선순위 큐 데이터 구조입니다.이 선택에 의해 알고리즘의 시간 복잡도가 달라집니다.일반적으로 priority 큐는 최소 비용으로 정점 v를 찾는 데 더 빠르지만 C[w] 값이 변경되면 더 비싼 업데이트를 수반합니다.

시간의 복잡성

프림의 알고리즘은 이 메이즈의 생성과 같이 랜덤 가중 그리드 그래프에 프림의 알고리즘을 적용하는 많은 응용 프로그램을 가지고 있습니다.

Prim 알고리즘의 시간 복잡도는 그래프에 사용되는 데이터 구조 및 가중치 기준으로 가장자리를 정렬하는 데 따라 달라지며, 이는 우선 큐를 사용하여 수행할 수 있습니다.다음 표에 일반적인 선택지를 나타냅니다.

최소 에지 가중치 데이터 구조 시간의 복잡성(합계)
인접 매트릭스, 검색
바이너리 힙 및 인접 리스트
피보나치 힙 및 인접 리스트

인접 매트릭스 또는 인접 리스트 그래프 표현을 사용하여 가중치 배열을 선형적으로 검색하여 추가할 최소 가중치 엣지를 찾는 Prim의 간단한 구현에는 O(V) 실행 시간이 필요합니다.그러나 이 실행 시간은 알고리즘 내부 루프에서 최소 무게 에지 찾기를 구현하기 위해 힙을 사용함으로써 훨씬 더 향상될 수 있습니다.

첫 번째 개선된 버전은 힙을 사용하여 무게에 따라 입력 그래프의 모든 모서리를 저장합니다.이로 인해 O(E log E)의 최악의 실행 시간이 발생합니다.그러나 가장자리 대신 정점을 저장하면 훨씬 더 개선될 수 있습니다.힙은 부분적으로 구성된 최소 스패닝 트리(MST)의 정점에 연결하는 최소 에지 가중치(또는 그러한 에지가 없는 경우 무한대)에 따라 정점을 정렬해야 합니다.MST에 정점 v를 선택하여 추가할 때마다 v가 w에 접속되도록 부분 MST 외부에 있는 모든 정점 w에 대해 감소 키 연산을 실시하여 키를 이전 값의 최소값과 (v,w)의 엣지 비용으로 설정한다.

간단한 이진 힙 데이터 구조를 사용하여 Prim의 알고리즘이 시간 O(E log V)에 실행됨을 보여줄 수 있습니다. 여기서 E는 에지 수, V는 정점 수입니다.그 그래프는 울창한 만큼 Eω(V)은, 1차 때 E적어도 V로그 V. 더 큰 밀도(일부 c을에 있는 적어도 Vc가장자리, 1)의 그래프의 경우, 프림 알고리즘 lin에 실행할 수 있다는 것이다에는 좀 더 정교한 피보나치 힙을 사용할 경우, 이 O(E+V로그 V)은 점근적으로 빠르게로 인하될 수 있다.귀fibonacci 힙 대신 d-ary [10][11]힙을 사용함으로써 시간을 더 쉽게 단축할 수 있습니다.

증거의 데모.이 경우 Y = Y - f + e 그래프는1 이미 Y와 같습니다.일반적으로 이 과정을 반복해야 할 수 있습니다.

정확성 증명

P를 연결된 가중 그래프라고 합니다.Prim 알고리즘이 반복될 때마다 하위 그래프의 정점과 하위 그래프 외부의 정점을 연결하는 에지를 찾아야 합니다.P가 연결되어 있기 때문에 모든 정점에 대한 경로가 항상 존재합니다.Prim 알고리즘의 출력 Y는 트리입니다. 트리 Y에 추가된 모서리와 정점이 연결되어 있기 때문입니다.Y를 그래프 P의 최소 스패닝트리로 하겠습니다1Y1=Y이면 Y는 최소 스패닝 트리입니다.그렇지 않으면 트리 Y에1 없는 트리 Y를 구성하는 동안 e를 첫 번째로 추가하고 V를 에지 e 앞에 추가된 에지로 연결된 정점 세트라고 가정합니다.다음으로 엣지 e의 한쪽 끝점은 세트 V에 있고 다른 한쪽 끝점은 세트 V에 없습니다.트리1 Y는 그래프 P의 스패닝트리이므로 트리 Y에는1 2개의 엔드포인트를 결합하는 경로가 있습니다.경로를 따라 이동할 때 집합 V의 정점과 집합 V에 없는 정점을 연결하는 가장자리 f를 만나야 합니다.트리 Y에 엣지 e가 추가된 반복에서 엣지 f도 추가될 수 있으며 무게가 e보다 작을 경우 엣지 e 대신 추가될 수 있습니다. 엣지 f가 추가되지 않았기 때문에 다음과 같이 결론지을 수 있습니다.

트리2 Y는 엣지 f를 제거하고 트리1 Y에 엣지 e를 더한 그래프라고 합니다.트리2 Y가 연결되어 있고, 트리1 Y와 같은 수의 에지를 가지고 있으며, 에지의 총 무게가 트리1 Y보다 크지 않음을 쉽게 알 수 있습니다.따라서 그래프 P의 최소 스패닝 트리이기도 하며, 세트 V의 구축 중에 추가된 에지 e와 그 앞에 추가된 모든 에지를 포함합니다.위의 단계를 반복하면 최종적으로 트리 Y와 동일한 그래프 P의 최소 스패닝트리를 얻을 수 있습니다.이는 Y가 최소 스패닝트리임을 나타냅니다.최소 스패닝 트리를 사용하면 서브 영역의 첫 번째 서브셋을 최소 서브셋X로 확장할 수 있습니다.

병렬 알고리즘

병렬 Prim 알고리즘을 위해 여러 프로세서 간에 분산된 인접 행렬입니다.알고리즘의 각 반복에서 모든 프로세서는 인접행렬의 컬럼 세트에 새로 삽입된 정점의 행을 검사함으로써 C의 일부를 갱신한다.그런 다음 결과가 수집되고 MST에 포함할 다음 정점이 전체적으로 선택됩니다.

Prim 알고리즘의 주요 루프는 본질적으로 순차적이므로 병렬화할 수 없습니다.그러나 사이클을 형성하지 않는 최소 무게의 다음 에지를 결정하는 내부 루프는 사용 가능한 프로세서 [12]간에 정점과 에지를 분할하여 병렬화할 수 있습니다.다음의 의사 코드에 의해서, 이것을 알 수 있습니다.

  1. 각 i에 길이 의 정점 세트를 합니다.
  2. 시퀀셜 알고리즘과 같이 C, E, F 및 Q를 작성하고 C, E 및 그래프를 모든 프로세서 간에 분할하여 각 프로세서가 착신 에지를 정점 세트로 유지합니다. })는 P_{에 저장되어 있는 C,E(\displaystyle E_{i})의 부품을 .
  3. Q가 비워질 때까지 다음 단계를 반복합니다.
    1. 모든 프로세서에서 : 최소값을 로 하는 솔루션)를 찾습니다.
    2. 국소해를 최소로 줄여 가능한 최소값인 C[v](글로벌 솔루션)를 갖는 정점 v를 구한다.
    3. 선택한 노드를 모든 프로세서에 브로드캐스트합니다.
    4. F에 v를 추가하고 E[v]가 특수 플래그 값이 아닌 경우 F에 E[v]도 추가합니다.
    5. 모든 프로세서에서 순차 알고리즘과 같이 }) })를 합니다.
  4. 반환 F

이 알고리즘은 일반적으로 공유 메모리 [13]시스템뿐만 아니라 분산[12] 시스템에도 구현할 수 있습니다.영사 시간은 O(V 2P)+O(V로그 ⁡ P){O({\tfrac{V^{2}}{P}})+O(V\log P)\displaystyle}, 수의 감소와 방송 작전 O에서(로그 ⁡ P)공유 메모리 machin에 프림 알고리즘의 변형 .[12]{O(P\log)\displaystyle}수행할 수 있다.에스,다른 정점에서 시작하여 Prim의 순차 알고리즘이 병렬로 실행되는 것도 탐구되었습니다.[14]단, 분산된 최소 스패닝트리 문제를 보다 효율적으로 해결하기 위한 보다 정교한 알고리즘이 존재함을 유의해야 합니다.

「 」를 참조해 주세요.

  • 최단 경로 문제에 대한 매우 유사한 알고리즘인 Dijkstra의 알고리즘
  • 탐욕은 프림의 알고리즘의 정확성을 이해하는 일반적인 방법을 제공한다.

레퍼런스

  1. ^ 를 클릭합니다Jarník, V. (1930), "O jistém problému minimálním" [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti (in Czech), 6 (4): 57–63, hdl:10338.dmlcz/500726.
  2. ^ 를 클릭합니다Prim, R. C. (November 1957), "Shortest connection networks And some generalizations", Bell System Technical Journal, 36 (6): 1389–1401, Bibcode:1957BSTJ...36.1389P, doi:10.1002/j.1538-7305.1957.tb01515.x.
  3. ^ 를 클릭합니다Dijkstra, E. W. (December 1959), "A note on two problems in connexion with graphs" (PDF), Numerische Mathematik, 1 (1): 269–271, CiteSeerX 10.1.1.165.7577, doi:10.1007/BF01386390, S2CID 123284777.
  4. ^ 를 클릭합니다Sedgewick, Robert; Wayne, Kevin Daniel (2011), Algorithms (4th ed.), Addison-Wesley, p. 628, ISBN 978-0-321-57351-3.
  5. ^ 를 클릭합니다Rosen, Kenneth (2011), Discrete Mathematics and Its Applications (7th ed.), McGraw-Hill Science, p. 798.
  6. ^ a b 를 클릭합니다Cheriton, David; Tarjan, Robert Endre (1976), "Finding minimum spanning trees", SIAM Journal on Computing, 5 (4): 724–742, doi:10.1137/0205051, MR 0446458.
  7. ^ a b 를 클릭합니다Pettie, Seth; Ramachandran, Vijaya (January 2002), "An optimal minimum spanning tree algorithm" (PDF), Journal of the ACM, 49 (1): 16–34, CiteSeerX 10.1.1.110.7670, doi:10.1145/505241.505243, MR 2148431, S2CID 5362916.
  8. ^ 를 클릭합니다Tarjan, Robert Endre (1983), "Chapter 6. Minimum spanning trees. 6.2. Three classical algorithms", Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, pp. 72–77.
  9. ^ 를 클릭합니다Kepner, Jeremy; Gilbert, John (2011), Graph Algorithms in the Language of Linear Algebra, Software, Environments, and Tools, vol. 22, Society for Industrial and Applied Mathematics, p. 55, ISBN 9780898719901.
  10. ^ a b 타잔(1983), 페이지 77.
  11. ^ 를 클릭합니다Johnson, Donald B. (December 1975), "Priority queues with update and finding minimum spanning trees", Information Processing Letters, 4 (3): 53–57, doi:10.1016/0020-0190(75)90001-0.
  12. ^ a b c Grama, Ananth; Gupta, Anshul; Karypis, George; Kumar, Vipin (2003), Introduction to Parallel Computing, pp. 444–446, ISBN 978-0201648652
  13. ^ Quinn, Michael J.; Deo, Narsingh (1984), "Parallel graph algorithms", ACM Computing Surveys, 16 (3): 319–348, doi:10.1145/2514.2515, S2CID 6833839
  14. ^ Setia, Rohit (2009), "A new parallel algorithm for minimum spanning tree problem" (PDF), Proc. International Conference on High Performance Computing (HiPC)

외부 링크