🚀 What I Will Learn

• 최소 신장 트리(Minimum Spanning Tree, MST)에 대해 이해하기

최소 신장 트리(Minimum Spanning Tree, MST)란? 그래프 내의 모든 정점을 포함하는 트리(=신장 트리: Spanning Tree) 중에서 사용된 간선들의 가중치 합이 최소인 트리

---

프림 알고리즘_최소 신장 트리(Minimum Spanning Tree, MST)

1️⃣ 최소 신장 트리(Minimum Spanning Tree, MST)란?

• 신장 트리란 특정한 그래프에서 모든 정점을 포함하는 그래프
• 최소 신장 트리는 스패닝 트리 중에서 간선의 가중치 합이 가장 작은 트리를 의미

최소 신장 트리: 모든 노드들을 연결할 때, 가장 적은 비용의 간선만 선택할 수 있도록 하는 것

✔️ 프림 알고리즘

1) 그래프에서 정점 하나를 선택해서 트리 T에 포함시킨다
2) T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 가중치가 가장 작은 간선을 찾는다
3) 해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킨다
4) 모든 모드가 포함될 때까지 2)와 3)을 반복한다

✔️ 프림 알고리즘의 동작 과정

1) 시작 노드인 1과 인접한 노드 중 가중치가 가장 작은 간선 찾기 ➡️ 1

2) 현재 트리 T인 4의 인접 노드 중 가중치가 가장 작은 간선 찾기 ➡️ 1

3) 현재 트리 T인 5의 인접 노드 중 가중치가 가장 작은 간선 찾기 ➡️ 1

4) 현재 트리 T인 3의 인접 노드 중 가중치가 가장 작은 간선 찾기 ➡️ 2

5) 최소 신장 트리 완료

• 가중치가 같은 경우가 존재할 수 있기 때문에 여러가지 경우의 수가 존재할 수 있다

프림 알고리즘은 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로 구현할 수 있다

---

✨ tl;dr

• 프림 알고리즘은 최소 스패닝 트리를 구하는 과정에서 𝑂(𝐸𝐿𝑜𝑔𝑉)의 시간 복잡도를 가진다

시간복잡도: 문제를 해결하는데 걸리는 시간과 입력의 함수 관계.
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것을 의미