알고리즘/개념
[알고리즘] 최소 신장 트리(MST) : 프림 알고리즘
- -
프림(Prim) 알고리즘
프림 알고리즘은 인접한 정점 중 최소비용으로 이동가능한 정점을 선택하면서 방문하는 알고리즘입니다.
즉, 인접 리스트를 사용한 정점들 간의 연결 관계가 필요하며, 이미 방문한 정점들에 대한 visit 정보를 기록합니다.
동작과정
- 최초 출발 정점에서 연결되어 있는 간선들 중 가중치가 최소인 것을 선택해서 신장 트리에 추가합니다.
- 신장 트리에 포함된 모든 정점들과 연결된 간선들 중 가중치가 최소인 것을 선택해서 신장 트리에 추가합니다.
- 간선의 개수가 V-1개가 될 때까지 반복합니다.
- 모든 정점들이 간선으로 연결이 됐으면 종료합니다.
아래의 예제 그래프의 동작 과정을 그림을 통해 알아보겠습니다.
모든 과정을 통하면 위와 같은 그래프 형태를 나타냅니다.
프림(Prim) 알고리즘은 크루스칼 알고리즘과 다르게 정점을 중심으로 동작하며, 그래프 탐색과 유사하게 동작합니다.
각 정점들과 연결된 간선들 중 최소인 간선을 선택하는 데에 우선순위 큐를 사용한다.
파이썬 예제 코드 - 우선순위 큐 사용
'알고리즘 > 개념' 카테고리의 다른 글
| [알고리즘] 위상 정렬 (0) | 2023.04.26 |
|---|---|
| [알고리즘] Union - Find 알고리즘 (0) | 2023.04.21 |
| [알고리즘] 최소 신장 트리(MST) : 크루스칼 알고리즘 (0) | 2023.04.21 |
| [알고리즘] 이분 탐색(Binary Search) (1) | 2023.04.14 |
| [알고리즘] 순열과 조합 (0) | 2023.04.11 |
Contents
소중한 공감 감사합니다