최소 비용 신장 트리(MST)

1. 최소 신장 트리(MST)

• 그래프에서 최소 비용 문제
  • 1) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
  • 2) 두 정점 사이의 최소 비용의 경로 찾기
• 신장 트리
  • n 개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
• 최소 신장 트리(Minimum Spanning Tree)
  • 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

---

---

2. Prim 알고리즘

• 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식
  • 1) 임의 정점을 하나 선택해서 시작
  • 2) 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
  • 3) 모든 정점이 선택될 때까지 1), 2) 과정을 반복
• 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지
  • 트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들
  • 비트리 정점들(nontree vertices) - 선택되지 않은 정점들

 

---

3. KRUSKAL 알고리즘