[Algorithms] Minimum Spanning Tree, Kruskal, Prim

MST (Minimum Spanning Tree)

  - https://sga8.tistory.com/32

[Data Structure] Graph, etc

 

Kruskal Algorithm (간선 위주의 알고리즘)

  - Greedy Method

  - 과정

    1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.

    2. 정렬된 간선 리스트에서 가장 낮은 가중치를 선택한다.

    3. 사이클이 형성된다면, 해당 간선을 제외하고 2번 과정을 다시 진행한다.

    4. 트리가 (N-1)개의 간선을 가지면 종료한다.

 

 

Prim Algorithm (정점 위주의 알고리즘)

  - spanning tree를 단계적으로 확장해나가는 방법 → 사이클 형성 여부 확인할 필요 없음!

  - 과정

    1. 시작 정점을 MST 집합에 포함한다.

    2. 인접한 정점 중에서 최소 간선으로 연결된 정점을 선택하여, MST 집합에 포함한다.

    3. 트리가 (N-1)개의 간선을 가지면 종료한다.