[알고리즘 기본]PRIM 알고리즘

PRIM 알고리즘

MST(최소 신장 트리)를 구현하는 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있다.

오늘은 프림 알고리즘에 대해 더 자세히 살펴보도록 하겠다.

 

프림 알고리즘을 시작점을 중심으로 방문 가능한 모든 정점을 방문해서 가장 최소 가중치를 가지는 노드와 연결하고,

이를 모든 정점을 방문할 때 까지 반복함으로써 최소 신장 트리를 구한다.

 

크루스칼은 프림에 비해 희소 그래프인 경우, 그러니까 간선이 적은 경우 적합하고,

프림은 크루스칼에 비해 간선이 많이 존재하는 밀집그래프에 더 적합하다.

 

크루스칼 알고리즘은 아래에서 더 자세하게 다룬다.

https://jinniepark.tistory.com/55

[알고리즘 기본]Kruskal 알고리즘

 

일단을 개념적으로 구하는 방법을 그려보았다.

---

예시)

 

 

초기 상태이다. 해당 정점을 방문했는지 체크할 visited배열과 가장 작은 가중치를 가질 Min_edge배열이 존재한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

 

하지만 위와 같은 방법으로 구현 할 때 인접해 있는 노드를 탐색하고 또 그 가중치를 비교하는 과정에서 정렬/비교를 하면 (주변 정점 수)-1번 만큼 연산이 이루어져야한다. 이는 많은 노드와 정점이 있다면 시간복잡도를 늘리는 원인이 된다.

따라서 실제 구현할때는 우선순위 큐를 사용해서 시간복잡도를 줄여야한다. 

 

아래에 우선순위 큐를 추가한 구현방법을 확인해보겠다.

 

 

 

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

관련문제

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

https://jinniepark.tistory.com/47

[백준][1197]최소 스패닝 트리