MST - 프림, 크루스칼 알고리즘

프림 알고리즘

• MST 구현에 사용되는 알고리즘
• 매 순간 최선의 선택을 하는 greedy 알고리즘
• 알고리즘 순서
  1. 시작 노드만 MST에 들어감
  2. 해당 시작 노드와 연결되어 있는 노드들 중 가중치가 가장 낮은(높은, 경우에 따라 ) 노드를 선택한다. 이미 MST에 들어가 있다면 pass
  3. 2) 번 과정을 MST 전체 개수가 전체 노드 개수와 같아질 때까지 진행한다.
• 시간 복잡도

• 노드마다 최소 간선 찾는 시간 O(logV)
• 탐색 시간 O(VlogV)
• 각 간선에 대해 힙에 넣는 과정 O(logV) * E -> O(ElogV)
• O(ElogV)

• 구현

---

크루스칼 알고리즘

• 최소 비용으로 + 사이클 형성 방지
• 알고리즘 순서
  1. 간선들을 가중치 순서대로 정렬
  2. 정렬된 가중치들 중 사이클을 형성하지 않는 간선 선택
  3. 선택된 간선들 MST에
  4. MST 집합의 개수가 V-1개가 될때까지 2,3 반복
• 구현 시 필요한 알고리즘 : Disjoint Set / Union-Find
  -시간 복잡도
• O(ElogE)

• 구현

참고

---

간선의 수가 적은 Sparse Graph의 경우 크루스칼 알고리즘이 유리하고 간선의 수가 많은 Dense Graph의 경우 프림 알고리즘이 유리