Prim의 MST 알고리즘을 이해할 수 있다.

Goal

  • Prim 알고리즘이란
  • Prim 알고리즘의 동작을 이해할 수 있다.
  • Prim 알고리즘을 구현할 수 있다.
  • Prim 알고리즘의 시간 복잡도

Prim 알고리즘이란

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

Prim 알고리즘의 동작

  1. 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.
  2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
    • 즉, 가장 낮은 가중치를 먼저 선택한다.
  3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.

Prim 알고리즘의 구체적인 동작 과정

Prim 알고리즘을 이용하여 MST(최소 비용 신장 트리)를 만드는 과정

Prim 알고리즘 구현

Prim 알고리즘의 시간 복잡도

관련된 Post

References