[DATA STRUCTURES - Graph] Kruskal’s Algorithm (크루스칼) — “간선 중심” Greedy MST

Kruskal 이란 , 가중치 그래프에서 MST (최소 스패닝 트리) 를 찾는 방법이다. 

 

MST 조건
- 모든 정점을 포함하되
- 사이클이 존재하면 안됨
- 간선의 수가 V-1 이여야 하며
총 가중치가 최소가 되어야 함! (단순 ST 와의 차이점.)

 

여기서 Kruskal은 가중치가 작은 간선부터 하나씩 고르고, 사이클이 생기면 버리는 것이다.

 

Greedy 알고리즘으로 분류되는 이유는 " 매 단계에서 가장 작은 간선을 고르는 지역 최적" 을 선택하기 때문인데,

그래도 누적이 돼서 전역 최적이 된다. 

 

 

 

KruskalMST(V,E):
  sort E by weight
  make-set(v) for all v in V
  T = ∅
  for each edge (u,v) in E:
      if find(u) != find(v):
          T = T ∪ {(u,v)}
          union(u,v)
      if |T| == |V|-1: break
  return T

 

Algorithm KruskalMST
Input: Graph G
Output: MST T
Begin
    T ← {};
    while( n(T) < n - 1 and G.E is not empty ) {
        (v, w) ← smallest edge of G.E;
        G.E ← G.E - {(v, w)};
        if no cycle in {(v, w)} ∪ T,
            T ← {(v, w)} ∪ T
    }
    if (n(T) < n - 1)
        cout << "No MST";
End Algorithm

 

Step1. 

T 를 초기화 한다.

여기서 T는 현재까지 선택한 MST 의 간선 집합이다. 처음에는 아무 간선도 선택 안 했으므로 공집합! 

 

While ()

현재 포함된 간선의 수는 n-1 이여야되니 해당 조건을 확인하고  , 확인할 간선이 남았는지도 확인!

해당 조건을 통과하면, G 에 있는 간선들 모음에서 가장 작은것들 빼고, 해당 것을 제외한 남은 애들만 남겨놓기 

(가중치가 가장 작은 간선 하나를 선택한다.) -> 이게 바로 Greedy

 

현재 MST 후보 T에 v,w 간선을 추가했을 때 사이클이 생기지 않는다면, 이 간선은 넣을 수 있다. 

(v,w 가 같은 컴포넌트에 있다면 cycle 이 발생한다.- DFS, BFS 로 경로 존재 여부를 검사해도 됨.) 사이클이 없다면 간선 집합에 추가한다. 

 

모든 간선을 다 봤는데도 v-1 조건을 만족하지 않는다면, MST 가 아니다!