프림 알고리즘이란?
가중치가 있는 연결된 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘
- 그래프에 간선이 많이 존재하는 밀집 그래프인 경우 적합하다.
- 시간 복잡도 - O(ElogV), 그래프가 충분히 뺵빽한 경우 피보나치 합을 이용하여 더 빠르게 값을 구할 수 있다.
설명
- 그래프에서 하나의 노드를 선택한 후 트리를 만든다.
- 그래프의 모든 간선이 들어있는 집합을 만든다.
- 모든 노드들을 방문하기 전까지 반복
- ->트리 자체와 연결된 간선들 중에서 가중치가 가장 작은 간선을 선택 후 연결되어 있는 노드로 넘어감.
- 반복이 끝났을 때 최소비용 신창트리가 완성!
관련 문제
섬 연결하기 - https://eoghks0521.tistory.com/15?category=732073
섬 연결하기(프로그래머스)
문제링크: https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 | 프로그래머스 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 알고리즘 설명: 가장 co..
eoghks0521.tistory.com
References
https://ko.wikipedia.org/wiki/프림_알고리즘
프림 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 생성나무를 찾는 알고리즘이다. 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 O ( E log V ) {\displaystyle {\color {Blue}O}(E\log V)}
ko.wikipedia.org
'알고리즘 > 이론' 카테고리의 다른 글
| LRU Cache Algorithm(Least Recently Used) (1) | 2019.11.03 |
|---|---|
| 깊이 우선 탐색(depth-first search, DFS) (0) | 2019.10.10 |
| 너비 우선 탐색(Breadth-first search, BFS) (0) | 2019.10.06 |
| 퀵 정렬(Quick sort) (0) | 2019.09.30 |
댓글