프림(Prim) 알고리즘

이전 포스팅에서 몇가지 알고리즘에 대해서 다룬 글이 있다.

자세한 내용은 아래 참고 포스팅 참고 바란다.

 

이번 포스팅은 프림 알고리즘 이라는것을 설명해볼 것이다.

 

우선 위키에서는 아래와 같이 소개한다.

 

 

https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

프림 알고리즘 - 위키백과, 우리 모두의 백과사전

 

좀더 쉽게 설명을 하면,

시작 정점에서 연결된 가장 작은 가중치의 간선을 확장해가면서 최소 신장트리를 만드는 알고리즘이다.

결론은 '최소 신장트리 알고리즘' 을 만들게 되고, 배열로 구현할 경우 시간복잡도는 o(n^2) / 힙으로 구현할 경우 시간복잡도는 O(E Log n) 이다.

Greedy 알고리즘의 일부이다.

 

과정

1. 어떤 점에서 시작하던 상관없다.
2. 그래프에서 임의의 하나의 정점을 선택한다.
3. 선택한 정점과 인접하는 정점들중 최소 비용의 간선이 존재하게되는 정점을 선택한다.
4. 2,3 과정을 반복 하여 모든 정점이 선택될까지 한다.

간단한 순서 예제 그림은 아래와 같다.

---

참고 포스팅

https://thenicesj.tistory.com/287

알고리즘 BFS 와 DFS

https://thenicesj.tistory.com/1070

다익스트라 알고리즘(Dijkstra)

https://thenicesj.tistory.com/284

시간복잡도 계산