프림 알고리즘(Prim Algorithm)

프림 알고리즘이란?(What is a Prime Algorithm)

---

프림 알고리즘은 최소 비용 신장 트리를 구하는 알고리즘중 하나이다. 가중치를 가지는 그래프에서 가장 작은 가중치를 가지는 엣지를 시작으로 인접한 정점과 연결된 엣지들중 가장 작은 가중치를 가지는 엣지들을 선택해 나가면서 신장 트리를 만드는 것이 프림 알고리즘이다. 프림 알고리즘이 엣지를 하나씩 선택한다는 점에서는 크루스칼 알고리즘과 같지만 인접한 정점의 엣지들만 선택한다는 점에서는 크루스칼 알고리즘과 다른 점을 보여준다. 다음은 프림 알고리즘 수행 과정이다.

 

그래프 및 가중치 표

다음은 프림 알고리즘에 사용될 그래프와 그래프의 가중치를 표로 나타낸 것이다. 그럼 프림 알고리즘을 수행해보자.

 

(4, 6) 선택

먼저 시작은 가장 작은 가중치를 가지는 엣지부터 시작한다. (4, 6)을 고르고 표에 표시한다.

 

(5, 6) 선택

인접한 정점중 5로 가는 엣지가 가장 가중치가 작기 때문에 (5, 6)을 고른다.

 

 

(2, 6) 선택

인접한 정점중 2로 가는 엣지가 가장 가중치가 작기 때문에 (2, 6)을 고른다.

 

 

(1, 2) 선택

인접한 정점중 1로 가는 엣지가 가장 가중치가 작기 때문에 (1, 2)을 고른다.

 

(0, 2) 선택

인접한 정점중 0으로 가는 엣지가 가장 가중치가 작기 때문에 (0, 2)을 고른다.

 

(0, 3) 선택

인접한 정점중 3으로 가는 엣지가 가장 가중치가 작기 때문에 (0, 3)을 고른다.

 

프림 알고리즘 종료

더 이상 수행하면 사이클이 생기기 때문에 프림 알고리즘은 여기서 종료한다. 다음은 프림 알고리즘 수행 과정을 gif로 나타낸 것이다.