최소 신장 트리(Minimum Spanning Tree, MST)

[devLupin]

• Spanning Tree : 모든 정점을 포함하는 sub tree 중 간선의 합이 최소인 트리

  • MST는 여러 개 일 수 있다.
  • 따라서 $V-1$개의 간선을 갖는다.
  • tree : 무방향이면서 사이클이 없는 그래프

• 사이클을 형성하지 않고, 최소 비용을 갖는 서브트리를 찾는 그리디 알고리즘이라고도 할 수 있겠다.

[devLupin]

Kruskal Algorithm

---

• 간선의 크기를 오름차순으로 정렬하고 제일 낮은 비용의 간선 선택
• 현재 선택한 간선이 정점 u, v를 연결하는 간선일 때
  • u, v가 같은 그룹이라면 continue
  • 다른 그룹이라면 같은 그룹으로 만들고, 현재 선택한 간선을 MST에 추가
• 다음으로 비용이 작은 간선 선택 후, 2번부터 반복
  • MST에 V-1개의 간선을 추가시켰다면 과정을 종료

[devLupin]

Prim Algorithm

---

• 임의의 정점을 선택해 MST에 추가, 해당 정점과 연결된 모든 간선을 PQ에 추가
• PQ에서 가장 비용이 적은 간선 선택
  • 해당 간선이 MST에 포함된 두 정점을 연결한다면 continue
  • 해당 간선이 MST에 포함된 정점 u와 포함되지 않은 정점 v를 연결한다면
    • 해당 간선과 정점 v를 MST에 추가 후 정점 v와 MST에 포함되지 않은 정점을 연결하는 모든 간선을 PQ에 추가
• MST에 V-1개의 간선이 추가될 때까지 반복