자료구조/알고리즘 - 프림 알고리즘

 

패스트캠퍼스 - 컴공전공 - 소프트웨어 베이직 - 프림 알고리즘

 

 

 

 

프림 알고리즘

 

1. 최소 신장 트리 (Minimum Spanning Tree, MST) 개념과 원리에 대한 이해

2. 프림 알고리즘을 이용, 최소 신장트리를 구현하는 방법

 

 

 

* 최소 신장 트리 (Minimum Spanning Tree, MST)

 

•신장 트리란 특정한 그래프에서 모든 정점을 포함하는 그래프

•최소 신장 트리는 스패닝 트리 중에서 간선의 가중치 합이 가장 작은 트리

 

 

패스트캠퍼스 강의자료

 

 

패스트캠퍼스 강의자료

 

위의 자료들에서 확인할 수 있는 것처럼

최소 신장 트리에서는 모든 노드를 연결하는데,

연결할 때 가장 적은 비용의 간선만 선택한다. 즉, 7만큼의 비용만을 소모하고 전체 노드를 연결하였다.

위의 일반적인 그래프에서 노드간의 연결에 24만큼의 비용을 소모했던 것과 대조적이다.

 

 

 

 

 

* 프림 알고리즘의 동작

 

 

1. 그래프에서 정점 하나를 선택해 트리 T에 포함

2. T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 가중치가 가장 작은 간선을 찾는다.

3. 해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함

4. 모든 노드가 포함될 때까지 2,3을 반복

 

패스트캠퍼스 강의자료

 

 

 

먼저, 1에서 시작한다고 가정했을 때

연결된 간선들 중 가중치가 가장 작은 간선을 찾는다.

 

 

패스트캠퍼스 강의자료

 

 

해당 간선과 연결된 노드를 트리에 포함하고,

다시 트리에 연결된 간선들 중 가중치가 가장 작은 간선을 찾고,

그 간선에 연결된 노드를 포함하고

...

모든 노드가 트리에 포함될 때까지 동일한 과정을 반복한다.

 

 

 

패스트캠퍼스 강의자료

 

패스트캠퍼스 강의자료

 

패스트캠퍼스 강의자료

패스트캠퍼스 강의자료

패스트캠퍼스 강의자료

패스트캠퍼스 강의자료

 

패스트캠퍼스 강의자료

패스트캠퍼스 강의자료

 

 

 

강의에서 다룬 위의 예시를 통해 프림 알고리즘이 동작하는 과정을 살펴볼 수 있었다.

( 최소 신장 트리 구하기 )

 

-> 프림 알고리즘은 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로 구현할 수 있다.

 

 

 

 

 

- 프림 알고리즘 구현해보기

 

 

 

 

 

 

 

 

 

역대급으로 길었던 메인함수를 가진 코드였다.

 

node 3, edge 3,

그리고 1,2,3을 연결하는 간선의 비용을 8,9,10으로 가정했을 때

프림 알고리즘을 이용, 최소 신장 트리 형태로 1,2,3을 연결하는 데 드는 비용이 17로 나오는 것이 정상이고,

출력 결과에서 마지막 줄에 나오긴 했으나

중간에 있는 0,8의 정체는 무엇인지 알 수가 없다..

 

이번 강의에서 매우 피곤해져서 당장 들여다보기는 어렵고

나중에 다시 들여다봐야할 듯

 

 

 

 

 

 

정리

 

 

프림 알고리즘은 최소 스패닝 트리(최소신장트리)를 구하는 과정에서 O(ElogV)의 시간 복잡도를 갖는다.

모든 간선에 대한 정보를 다 큐에 넣어서 처리한다는 점에서 E라는 시간이 소요되고,

큐에서 어떠한 원소를 꺼낼 때 logV라는 높이를 가질 수 있기 때문에

결과적으로 ElogV의 시간복잡도를 갖게 된다.