[알고리즘] 프림 알고리즘 Prim's Algorithm

프림 알고리즘 Prim's Algorithm이란?

최소 비용 신장 트리를 구현하는 알고리즘으로, 시작 정점에서부터 가중치의 합이 최소가 되도록 신장 트리를 확장해나가는 알고리즘이다.

 

프림 알고리즘의 동작

프림 알고리즘은 매번 최적의 선택을 하는 그리디 알고리즘에 기반하여 동작한다. 따라서 노드를 이동하는 순간순간마다 비용이 최소인 간선과 연결된 노드를 신장 트리 집합에 추가한다.

 

정점의 집합 = V

신장 트리(MST)에 추가되는 정점의 집합 = Y

MST에 추가되는 간선의 집합 = F

 

1. 맨 처음에는 시작 정점만이 Y에 추가된다.

2. Y와 인접한 노드 중 가장 낮은 비용인 간선과 연결된 노드를 Y에 추가하고 해당 간선도 F에 추가한다. 이 때 사이클이 발생해서는 안 된다.

3. Y=V가 될 때까지 2번 과정을 반복한다.

 

 

이 그래프의 MST를 프림 알고리즘으로 구해보자. 시작 정점은 V1이다.

 

V1과 인접한 노드 V2와 V3 중 비용이 가장 낮은 간선은 ((V1, V2))이고 이 간선과 연결된 노드는 V2이다. V2를 Y에, ((V1, V2))를 F 집합에 넣는다.

Y = {V1, V2}

F = {((V1, V2))}

 

집합 Y = {V1, V2}와 인접한 노드 V3과 V4 중 비용이 더 낮은 간선과 연결된 노드는 V3이다.

Y = {V1, V2, V3}

F = {((V1, V2)), ((V1, V3))}

 

 

집합 Y = {V1, V2, V3}과 인접한 노드 V4, V5 중 비용이 더 낮은 간선과 연결된 노드는 V5이다.

Y = {V1, V2, V3, V5}

F = {((V1, V2)), ((V1, V3)), ((V3, V5))}

사이클이 생기면 안 되기 때문에 간선 V2, V3은 선택되지 않는다.

 

 

집합 Y = {V1, V2, V3, V5}와 인접한 노드 중 비용이 가장 낮은 간선으로 연결된 노드는 V4이다.

Y = {V1, V2, V3, V5, V4}

F = {((V1, V2)), ((V1, V3)), ((V3, V5)), ((V3, V4))}

집합 Y가 V와 같아졌기 때문에 알고리즘이 끝난다.

총 비용은 1 + 3 + 2 + 4 = 10이다.