[Programming] Minimum Cost Spanning Tree(MST): Kruskals Algorithm

Minimum Cost Spanning Tree(MST): Kruskals Algorithm

---

포스트 난이도: HOO_Middle

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

---

 

# Minimum Cost Spanning Tree(MST): Kruskals Algorithm

 

이번 포스트에서는 MST의 대표적인 알고리즘 방식인 Kruskals algorithm에 대해서 살펴보도록 하겠다.

예제를 통해서 Kruskals algorithm을 살펴보도록 하자.

예제 코드가 필요한 Bro는 댓글로 알려주면 필자가 추가 포스트를 하도록 하겠다.

Kruskals algorithm 예제를 살펴보기에 앞서서 사실상 몇 가지 특징만 이해하면 끝이다.

첫 번째로는 Prims algorithm과 달리 연결 노드를 신경 쓰지 말고 제일 작은 edge들을 찾는다.

두 번째로는 MST의 주요한 특징 중 하나인 Cycle이 되지 않도록 유의한다.

사실 이 두 가지 특징이 Kruskals algorithm의 주요 특징이다.

 

 

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

여기서 MST를 찾을 것인데 Kruskals algorithm 방식으로 MST를 찾아본다고 가정했을 때,

제일 작은 edge인 5부터 시작하는 걸 알 수 있다.

 

 

이처럼 5가 제일 작은 edge이기에 선택이 되고 다음 작은 edge를 찾아주면 된다.

하지만 항상 Kruskals algorithm에서 유의할 점은 Cycle이 되지 않도록 확인해야 한다.

 

 

단계를 반복하다 보면 이렇게 5개의 노드에서 4개의 edge를 가진 MST가 완성된다.

이러한 알고리즘 방식을 우리는 Kruskals algorithm이라고 부른다.

이번 예제에서는 Cycle이 될 수 있는 경우가 발생하지는 않았지만 항상 Cycle이 되지 않도록 유의하여야 한다.

Cycle이 될 것 같다면, 해당 Edge는 포기하고 다음 최솟값 Edge를 선택하여 MST를 완성하면 된다.

Kruskals algorithm의 time complexity는 O(nlogn)과 O(n^2)이 나온다.

---

# In conclusion, 3줄 요약

1. MST의 Kruskals algorithm에 대해서 살펴보았다.

2. Kruskals algorithm은 최솟값 edge를 찾아가며 MST를 완성한다.

3. Cycle이 될 것 같다면 해당 edge는 포기하고 다음 최솟값 edge를 선택한다.

---