[알고리즘] Minimum Spanning Tree - Prim Algorithm vs. Kruskal Algorithm

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

Greedy Algorithms

---

답을 찾기 위해서 선택을 반복하는 알고리즘이다.

비교적 간단한 기준으로 답을 계속 골라 담고, 이를 바꾸지 않는다.

 

 

Minimum Spanning Tree

---

모든 node를 포함하며, edge cost가 최소가 되는 connected acyclic graph 찾기!

 

Given a Graph, find Subset of Edges so that a Connected Graph results with Minimum Sum of Edge Costs.

- minimum : edge cost가 최소가 되는

- spanning : 전체를 덮는, 즉 모든 node를 포함하는

 

 

Input

- node n개, edge m개로 이루어진 무방향 연결 그래프

- edge들에는 weight(비용)이 존재한다.

 

즉, MST는 edge cost가 최소가 되도록 하는 n-1개의 edge들을 선택하는 문제와 같다.

 

 

Algorithms

- Prim

- Kruskal

 

 

Prim Algorithm vs. Kruskal Algorithm

---

Prim Algorithm

• 시작점이 하나 존재한다. → 거기서부터 edge를 계속 붙여 나간다.
• cycle이 생기는지를 확인하는 방법
  : 선택한 edge가 연결하는 node는 이미 tree에 들어가 있는 node인가?
• Performance: O(MlogN)

Algorithm과 그의 Correctness 증명 (링크 박아넣을 예정)

 

Kruskal Algorithm

• 시작점이 없다. → edge를 아무데서나, weight이 작은 순으로 계속 끼워 넣는다.
• cycle이 생기는지를 확인하는 방법
  : 선택한 edge가 같은 덩어리(connected component)에 있는 node들을 연결하는가? (by. Union-Find)
• Performance: O(MlogM)

 

Algorithm과 그의 Correctness 증명 (링크 박아넣을 예정)