[알고리즘] Minimum Cost Spanning Tree(MST): Prims Algorithm

Minimum Cost Spanning Tree(MST): Prims Algorithm

---

포스트 난이도: HOO_Middle

[Notice] 포스트 난이도에 대한 설명

---

 

# Minimum Cost Spanning Tree(MST): Prims Algorithm

 

이번 포스트는 Middle 난이도의 포스트이기에 MST에 대한 설명은 생략하고 Prims algorithm에 대해서 살펴보겠다.

Prims란 MST의 특징을 가진 알고리즘으로써,

실제로 프로그래밍에서 MST에 대한 특징을 구현하고 싶을 때 사용하는 대표적인 방식이다.

Prims algorithm에 대한 개념 프로세스와 개념에 대한 이해를 예제를 통해서 살펴보도록 하겠다.

 

 

예를 들어 위와 같은 예제가 있다고 가정해보자.

여기서 MST를 구해야하는데 Prims algorithm 방식을 사용하여 찾아보도록 하겠다.

Prims algorithm에서 중요한 건 제일 작은 edge 값을 찾는 것이다.

그것이 바로 Prims algorithm의 시작점이 된다.

 

 

첫 번째 Edge는 5라는 전체에서 최솟값으로써 1과 4라는 노드를 연결해주고 있다.

여기서 유의할 점은 그다음 최솟값을 구하는 거지만 기존에 연결된 노드에서의 다음 최솟값 edge를 찾아야 한다.

한마디로 무작정 최소 edge를 찾는 것이 아니라 현재 연결되어 있는

노드 1과 노드 4와 근접한 edge 중에서 최소값 edge를 찾아준다.

 

 

다음 최솟값 edge는 9라는 것을 확인할 수 있다.

그러면 이제 노드 1과 노드 3 그리고 노드 4에 연결되어 있는 edges 중에서 최솟값을 찾아 표시해주면 된다.

이를 계속 반복하다보면 MST가 완성된다.

 

 

 

예제에는 5개의 노드가 있으니 edge는 4개가 나오는 걸 알 수 있다.

4개의 edge가 나옴으로써 MST가 만들어진 걸 확인할 수 있다.

이렇게 작동하는 방식이 바로 Prims algorithm이다.

---

# In conclusion, 3줄 요약

1. MST에는 대표적인 두 가지 알고리즘 방식이 존재한다.

2. 이번 포스트에서는 Prims algorithm 방식을 살펴보았다.

3. 연결된 노드에서 최솟값 edge를 찾는 것이 핵심이다.

---