[알고리즘] 최소 신장 트리(MST) - KRUSKAL 알고리즘

• 그래프에서 최소 비용 문제
  1. 모든 정점 연결 간선들 가중치 합이 최소가 되는 트리
  2. 두 정점 사이 최소 비용 경로 찾기

• 신장 트리 : n개 정점 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
• 최소 신장 트리(Minimum Spanning Tree) : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리

---

< KRUSKAL 알고리즘 > : 서로소 집합 사용

• 간선을 하나씩 선택해서 MST 를 찾는 알고리즘
  1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬(최대신장트리는 내림차순)
  2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 - 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택(union 연산 실패 상황)
  3. n-1 개의 간선이 선택될 때까지 2를 반복
• 간선을 선택하여 경로를 만드는 것은 union 연산과 같다.
• union - find 연산을 안 쓰면 사이클이 존재하는 지 검사할 알고리즘이 필요함. 반면 union 쓰면 같은 부모인지 체크해서 같다면 실패띄우고 다른 부모라면 간선 연결할 수 있다.
• 만약 그래프 정보가 인접행렬이나 인접리스트로 주어진다면 크루스칼 알고리즘을 쓰기 위해서 간선리스트로 변환하는 작업이 필요하다.

---

MST-KRUSKAL(G, w)

    for vertex v in G.V                     //G.V : 그래프의 정점 집합
        Make_Set(v)                        //G.E : 그래프의 간선 집합


    G.E에 포함된 간선들을 가중치 w에 의해 정렬


    for 가중치가 가장 낮은 간선 (u,v) : n-1 개 간선 선택될 때까지
       if Find_Set(u) != Find_Set(v)
           A = A 합집합 {(u,v)}
           Union(u,v);