{ Prim }

  • 자료구조 - MST 학습 - Prim algorithm

    |

    Prim algorithm

    1. 정점 하나를 가진 트리에서 시작
      • TV = {v1}
        • TV : 트리의 정점
    2. 트리 내의 정점 u와 트리 밖의 정점 v를 잇는 Edge 중 최소 비용을 가진 (u,v)를 트리 Edge로 만든다.
      • TE = TV U {u,v}
    3. 트리 밖의 정점 v도 트리의 정점으로 만든다.
      • TV = TV U {v}
    4. TV = V(G)와 같아지면 종료