728x90
프림 알고리즘
시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법
- 정점선택을 기반으로 하는 알고리즘
- 이전 단계에서 만들어진 신장 트리를 확장하는 방법
동작과정
1. 시작 단계에서는 시작 정점만이 MST집합에 포함
2. 앞 단계에서 만들어진 MST집합에 인접한정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장
(가장 낮은 가중치를 선택)
3. 위의 과정을 트리가 N-1개의 간선을 가질때까지 반복
시간복잡도
주 반복문이 정점의 수 N만큼 반복하고 내부 반복문이 N번 반복
- 프림 알고리즘의 시간복잡도 O(n^2)
- 그래프에 간선이 많이 존재하는 밀집 그래프에 프림 알고리즘이 적합
'자료구조' 카테고리의 다른 글
| 트리 순회 (tree traversal), 전위순회, 중위순회, 후위순회 (2) | 2021.05.10 |
|---|---|
| 탐색 (Search), 순차 탐색, 이진 탐색, 색인 순차 탐색, 보간 탐색 (0) | 2021.05.10 |
| 크루스칼 알고리즘 (Kruskal MST) (0) | 2021.05.08 |
| 신장트리 (Spanning Tree), 최소 신장트리 (Minimum Spanning Tree) (0) | 2021.05.08 |
| DFS(깊이 우선 탐색), BFS(너비 우선 탐색) (0) | 2021.05.08 |