Minimum Spanning Trees 최소신장트리

최소신장트리란?

spanning tree(신장트리)란 모든 정점(vertex)를 포함하고, 이 정점들을 연결하는 간선(edge)로 이루어진 tree이다.

=> tree라는 조건을 만족시켜야 하기 때문에 모든 정점들이 연결되어있고, 사이클이 없다 (acycle, connected)

* 주어진 그래프에서 어떤 edge를 선택하냐에 따라 다양한 spanning tree를 만들 수 있다.

* spanning tree의 cost : 선택한 edge들의 모든 weight 합

=> spanning tree cost가 가장 작은 spanning tree를 minimun spanning tree (최소신장트리)라고 한다.

 

신장트리 만들기

GENERIC-MST(G, w)
    A = Ø
    while A does not form a spanning tree
          do find an edge (u, v) that is safe for A
          A = A ∪{(u, v)}
    return A

A : MST를 만족하는 edge set

=> 그래프에서 A에 포함했을 때 MST를 만족하는 edge를 하나씩 추가해준다

 

 

프림 알고리즘 (Prim's Algorithm)

이동할 수 있는 vertex까지의 weight 가 최솟값인 vertex를 반복해서 선택하는 방법!

=> 이 때 최소값을 저장할 자료구조에 따라 시간복잡도에 차이가 생긴다

(일반 배열에 넣으면 최소값 찾기에 n 소요, min_heap을 이용해주면 logn 소요)

 

1. 찾기를 시작할 source vertex를 선택한다.

    배열(혹은 min_heap)에는 각 vertex별로 distance, pre를 담아둔다

    (distance : 지금 vertex로 올때의 weight)

    (pre : 지금 vertex로 올때 이전 vertex)

    source vectex의 distance는 0, pre는 자기자신

    나머지 vertex의 distance 초기값은 무한대 (MAX)

2. 반복시작! (반복 시작할때 선택한 vertex는 source vetex임)

3. 지금 선택한 vertex를 기준으로 배열을 업데이트 해주는데...

    a. 선택한 vertex와 edge로 연결된 모든 vertex의 distance와 pre를 업데이트한다.

        distance는 선택한 vertex와 연결된 edge의 weight값인데..

        기존에 저장되어 있던 distance와 비교해서

        (1) 기존에 저장되어 있던 distance보다 weight가 적으면, 새롭게 업데이트해준다

              (distance는 weight, pre는 선택한 vertex)

        (2) 아닌경우 그대로 유지해준다

    b. 연결된 모든 vertex를 위와 같이 업데이트 해준다

4. 업데이트 한 정보를 바탕으로 distance가 가장 작은 vertex가 다음에 이동할 vertex임!

    (이 때 최소값이 여러개인경우, random으로 선택한다. 선택에 따라 여러개의 MST가 생기는것)

    (아직 방문하지 않은 vertex로만 간다)

5. 2번으로 돌아간다 (계속반복)

    모든 vertex에 방문했으면, 반복을 종료해준다.

6. 반복이 종료됐을 시점에 각 vertex다의 pre와의 edge가 MST에 포함되는 edge가 되는것!

 

=> 그냥 배열을 사용하면, 가장 작은 vertex를 선택할 때 O(n)의 시간복잡도가

=> min_heap을 사용해주면, 가장 작은 vertex를 선택할 때 O(logn)의 시간복잡도가 필요함

    이 때 min_heap을 사용하면 3번 단계에서 각 노드를 업데이트할때마다, heapify (heap 정렬)을 새롭게 해주어야 한다.

 

MST-PRIM(G, w, r)
1 for each u ∈ G.V
2      u.key = ∞
3      u.π = NIL
4 r.key = 0
5 Q = G.V
6 while Q ≠ Ø
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9           if v ∈ Q and w(u, v) < v.key
10                v.π = u
11                v.key = w(u, v)
12                decrease-key(G, v, v.key)

G : 그래프

W : weight

r   : root (source vertex)

Q  : min_heap

 

1 ~ 4 : 각 vertex의 key(distance)와 pre(π) 를 초기값으로 업데이트 해준다.

            root (source)의 key(distance)는 0이된다.

5       : min_heap에 각 vertex 넣어주가

6 ~ 12 : 반복시작 (모든 vertex를 업데이트)

           u : distance가 min인 vertex

           v : u의 인접 vertex들 (즉 v를 업데이트 해주는것!)

           decrease-key : heapify하는것 (업데이트된 vertex에 맞게 heap 만들기)

 

 

 

크루스칼 알고리즘 (Kruskal's Algorithm)

disjoint set으로 MST를 구하는 방법

=> 무조건 weight가 작은것끼리 묶어가면서 만든다!

 

1. 초기에는 각각의 vertex가 disjoint set이 된다.

2. 반복 시작

3. 전체 edge 중 weight가 가장 작은 edge를 만드는 vertex 두개를 union해준다.

    (가장 작은 edge가 여러개인경우 random으로 선택)

    두 vertex의 disjoint set을 union 해주는것!

    이 때 edge를 구성하는 vertex가 포함된 set을 찾을 때 FIND-SET연산을 이용한다 (disjoint-set 에 대한 내용 참고)

    == parent가 변경된다. (union 알아서 할 수 있음!)

    find-set을 통해 edge를 구성하는 vertex가 기존에 같은 set에 있었는지 확인할 수 있다 (return값을 비교)

    a. 같은 set에 있었으면, 해당 edge는 MST 에 포함될 수 없는것! (cycle이 생겨 tree라는 조건만족을 못함)

    b. 다른 set에 있었으면, 해당 edge를 MST에 포함시켜주고, 두 set을 union해준다.

4. 2번으로 돌아간다.

    최종적으로 남은 set이 한개일때까지 반복한다.

    (혹은 모든 edge에 대해 반복을 진행해줘도 가능! 하지만 set의 parent가 바뀌게 된다 (find))

 

MST-KRUSKAL(G, w)
1 A = Ø
2 for each vertex v ∈ G.V
3      MAKE-SET(v)
4 sort the edges of G.E into nondecreasing order by weight w
5 for each edge (u, v) ∈ G.E, taken in nondecreasing order by weight
6      if FIND-SET(u) ≠ FIND-SET(v)
7           A = A ∪ {(u, v)}
8           UNION(u, v)
9 return A

 

2 ~ 3 : 각각의 vertex마다 set을 만들어주고, weight를 기준으로 edge를 정렬해준다

4       : 반복하는 부분!

           FIND-SET(u) 와 FIND-SET(v)를 비교하는 부분에서 해당 edge를 MST에 포함할지 말지를 결정한다