최소 신장 트리 구하기 : 프림(Prim's) 알고리즘

프림 알고리즘은 최소 신장 트리를 구하는 데 사용한다.

(최소 신장 트리를 구하는 또다른 방법으로 크루스칼 알고리즘이 있는데, 이에 대한 글은 여기서 보면 된다.)

https://woo-niverse.tistory.com/227

최소 신장 트리 구하기 : 크루스칼(Kruskal) 알고리즘

 

 

프림 알고리즘

- 매순간의 최선의 조건을 선택하는 그리디 알고리즘

- 인접 정점들 중에서 가중치가 가장 작은 간선으로 연결된 정점을 찾는다

- 간선을 중심으로 하는 크루스칼 알고리즘과 다르게, 프림 알고리즘은 정점을 기준으로 찾는다

- 최소 힙으로 구현할 수 있다

 

동작 과정

(1) 최소신장트리 집합에 임의의 시작 정점을 넣는다

노드A를 시작 정점으로 한다

집합: [A]

 

(2) 인접한 정점들 가운데 가중치가 가장 작은 간선으로 연결된 정점을 집합에 넣는다

- 이때, 집합에 속해 있지 않은 정점들을 대상으로 한다 (사이클 방지)

노드A와 인접한 노드들 중에서 가중치가 가장 작은 정점 C 를 연결하고 집합에 넣는다

집합 : [A, C]

 

노드A, C와 인접한 노드들 중에서 가중치가 가장 작은 정점 B를 연결하고 집합에 넣는다

집합 : [A, C, B]

 

노드A, C, B와 인접한 노드들 중에서 가중치가 가장 작은 정점 B를 연결하고 집합에 넣는다

집합 : [A, C, B, D]

(이전에 선택된 노드B를 기준으로 하는 게 아니라, 현재 최소신장트리 집합 안에 들어있는 노드들을 기준으로 한다!)

 

 

(3) 최소신장트리 집합의 원소 개수가 원본 그래프 정점의 개수와 일치할 때까지 (2)를 반복한다

집합 : [A, C, B, D, E, F]

 

 

시간복잡도

그래프를 힙으로 구현했을 때의 시간복잡도를 알아보자. V는 정점의 개수, E는 간선의 개수다.

 

힙에서 최솟값을 추출하는 데 소요되는 시간복잡도 $O(\log V)$, 이때 모든 정점을 대상으로 하기 때문에 $O(V \log V)$ 이다.

따라서 탐색 과정에 드는 시간복잡도는 $O(V \log V)$이다.

 

그리고 각 노드의 인접 간선을 찾는 데 소요되는 최대 시간복잡도 $O(E)$, 힙에 push하는 과정이 $O( \log V)$ 이다.

따라서 힙을 구성하는 데 드는 시간 복잡도는 $O(E \log V)$이다.

 

최종적으로 $O(V \log V + E \log V)$ 에서, 일반적으로 E가 V보다 크기 때문에 $O(E \log V)$ 가 된다

 

 

파이썬 코드

백준 1197번 최소 스패닝 트리 예제를 통해 알아보자

https://woo-niverse.tistory.com/228

[백준/약점체크] 1197번: 최소 스패닝 트리