prim 썸네일형 리스트형 Prim's algorithm using priority_queue Prim 알고리즘 개요 가중치가 있는 무방향 그래프에서 MST(최소 스패닝 트리)를 구할 때 Prim's 알고리즘을 이용할 수 있다. 본 포스팅에서는 인접 리스트로 표현된 그래프에서 PQ 자료구조를 이용해 MST를 구하는 방법을 알아 본다. 시간 복잡도는 O(E log(V)) 가 된다. ※ 참고: 인접 행렬로 구한 Prim 알고리즘 : O(V^2) Prim 알고리즘에 PQ를 이용하기 위해서는 아래 두가지 연산이 필요하다. - ExtractMin: MST에 아직 포함되지 않은 모든 정점에서 최소 키 값을 가진 정점을 가져온다. - DecreaseKey: 정점을 추출한 후 인접한 정점의 키를 업데이트 해야 하며, 새 키가 더 작으면 업데이트 한다. 알고리즘 1) 모든 정점을 무한 값을 키 값으로 가지게 초기.. 더보기 이전 1 다음