프림 알고리즘: 두 판 사이의 차이

'''프림 알고리즘'''(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>]]까지 떨어진다.