핵심
내용
Prim(프림) 알고리즘이란?
NOTE
•
MST를 찾는 알고리즘 중 하나 (무방향 그래프)
•
인접한 정점 중 최소비용으로 이동 가능한 정점을 선택하면서 방문하는 알고리즘
•
크루스칼 알고리즘과 같은 용도지만, 응용상황에 따라 두 알고리즘의 효율성이 달라짐
◦
Kruskal : 간선을 기준으로 판단
◦
Prim : 정점을 기준으로 판단
•
정점 1000, 간선 100만의 경우(완전그래프) 시간복잡도 ( 간선은 대충 100만개 있다 가정)
◦
인접행렬 → O(2V^2) → 200만
◦
인접리스트 ( 우선순위 큐 사용X ) → O(V^2 + E) → 100만 + 100만 → 200만
◦
인접리스트 ( 우선순위 큐 사용O ) → O((V+E) log V) → 200만 * log 1000 → 1000만
▪
탐색 시간 : O( V log V)
•
모든 노드의 탐색 : V
•
최소 간선을 찾는 시간 : log V
▪
우선순위 큐 구성 O ( E log V)
•
각 노드의 인접 간선을 찾는시간은 각 노드의 차수 O(2E) → O(E)
•
간선에 대해 힙에 넣는 과정 O(logV)
Prim 알고리즘 - 그림으로 이해하기
NOTE
1.
시작정점으로 부터 최소 비용을 가진 간선을 선택한다
2.
선택된 간선에 연결된 정점 중에 가장 최소 비용을 선택한다 (방문하지 않은 정점 중)
Prim 알고리즘 - 코드구현 (인접행렬)
NOTE
•
인접리스트 → O(V^2+E) → 완전 그래프인 경우에는 크게 이득이 없음
•
인접행렬 → O(2 V^2)
코드
Prim 알고리즘 - 코드구현 (우선순위 큐)
NOTE
코드