Minimum Spanning Tree

---

created : 2023-12-15

---

What I Learned

Minimum Spanning Tree 란 ?

가중치가 있고 방향성이 없는 그래프 G
G의 subgraph g 중
1. Tree 이면서 (connected & acyclic(사이클이 없는))
2. 모든 정점을 포함하고 (Spanning)
3. 간선들의 가중치 합이 가장 작은(Minimum) subgrpah

활용 예
연결 자원 가능한 적게 쓰며, 모든 지점 연결되도록 할 때 사용
Ex) 컴퓨터망 구성

Tree의 특징

• 포함된 V개의 정점을 최소 수의 간선(V-1개) 사용해 모두 연결하는 구조
• 하나의 간선만 제거해도 비연결이 된다.
• 하나의 간선만 추가해도 사이클이 생긴다.

MST의 특징

Partition Of Graph : G의 정점 중 1 ~ V-1 개 정점으로 이루어진 부분집합

Crossing Edge : partition과 나머지 정점들 간에 연결하는 간선

• 입력 그래프 G에 V개의 정점이 있다면, MST는 V-1개의 간선을 포함
• G에 대한 모든 가능한 partitioning에 대해 crossing edge 중 하나는 반드시 MST에 포함
• 이때, 최소 가중치를 가지는 crossing edge가 반드시 포함된다.

그래프에서 MST를 찾는 방법

• Greedy MST 알고리즘
  - 아무 간선 포함 않은 상태에서 시작
  - 아직 서로 연결 안 한 partition 찾기
  - Crossing edge 중 weight 가장 작은 간선 MST에 포함
  그래프가 커지면 partition 수 매우 많아지며, 이 중 연결 안 한 partition 잘 찾는 방법 필요
  
• Kruskal's 알고리즘
  - 아무 간선 포함 않은 상태에서 시작
  - 간선을 weight의 오름차순에 따라 하나씩 검사
  - 추가했을 때, Cycle을 만들지 않는 간선이라면 MST에 추가
  - 총 V-1개 간선 포함 시 종료
  
• Prim's 알고리즘
  - 아무 간선 포함 않은 상태에서 시작
  - 정점 0은 MST에 포함된 상태라 봄
  - MST와 나머지 정점 연결하는 간선 중
  - weight 가장 작은 간선을 MST에 추가하는 것 반복
  - 총 V-1개 간선 포함하면 종료

Kruskal's 알고리즘

중요한 조건으로 추가했을 때 Cycle을 만들지 않는 간선을 추가한다는 조건이 있다.
Cycle을 형성하는 간선을 추가한다면, Tree의 성질을 잃어버린다.

Kruskal 알고리즘은 Greedy 알고리즘에 포함된다.
그 이유는, Cycle을 형성하지 않는 간선은 정점 2개를 다른 파티션에 두는 것으로
서로 연결 안한 partition의 최소 가중치 간선을 추가하기 때문이다.

Cycle 안 만드는 간선을 체크하는 방법
1. DFS
추가하려는 간선을 따라 DFS로 탐색하여 자신으로 되돌아 오는 경로가 있는지 확인하는 방법
MST에 포함된 정점이 V개, 간선이 E 개라면 Cycle 탐지하는 데 걸리는 시간은 ?
Worst Case (Cycle형성 X) -> 새로 추가된 정점과 MST에 포함된 정점을 확인해야함 (V)

2. Union & Find
   Union(a, b) : 정점 a와 b를 간선으로 연결하고 같은 Component Id로 저장
   Connected(a, b) : a와 b가 연결되어 있는지 확인 (같은 컴포넌트에 속하는 지)
   Union의 비용 -> Weighted Quick Union 방식 사용
   a의 root 찾는 비용 logV
   b의 root 찾는 비용 logV ,,, 따라서 logV 비례한 시간
   Connected의 비용 -> a, b의 root 비교 -> logV 비례한 시간
   따라서, Union & Find 방식을 활용하여 O(log V)에 비례한 시간에 Cycle 체크 가능

Kruskal 알고리즘의 비용
Priority Queue에 간선 추가 비용 : O(log E)
간선 추가 횟수 : E

Priority Queue에 간선 삭제 비용 : O(log E)
간선 삭제 횟수 : E (Worst Case 모든 간선을 다 체크해봐야 할 수 있음)

Cycle 탐지 비용 : O(log V)
횟수 : E

Union 비용 : O(log V)
횟수 : V

정점의 수(V) 보다 간선의 수가 많다고 가정했을 때 : ~O(E * log E)이 비례한 시간 걸린다.

Prim's 알고리즘 (Lazy 와 Eager)

MST와 나머지 정점 연결하는 간선 중 weight 가장 작은 간선을 MST에 추가하는 것을 반복
Prim 알고리즘도 마찬가지고 Greedy 알고리즘에 포함된다.
시작 정점을 MST에 포함된 상태라고 여기고
MST와 나머지 정점 연결하는 간선을 선택할 때
MST partition과 나머지 정점을 연결되지 않은 Partition으로 볼 수 있기 때문이다.
즉, 서로 연결 안 한 partition 연결을 반복하는 알고리즘으로 볼 수 있다.

MST와 나머지 정점을 연결하는 최소 간선을 찾는 효율적인 방법
1. 모든 간선 차례로 다 확인해보기
시간이 너무 오래 걸리는 비효율적인 탐색

2. minPQ 활용
   최소 weight 간선 찾는데 logE 비용으로 줄일 수 있음

Prim 알고리즘의 비용
PQ 간선 추가 비용 : log(E)
간선 추가 횟수 : E

PQ 간선 삭제 비용 : log(E)
간선 삭제 횟수 : E (Worst Case 모든 간선을 다 체크해봐야 할 수 있음)

include 확인 비용 : 상수시간
횟수 : E

include 변경 비용 : 상수시간
횟수 : V
정점의 수(V) 보다 간선의 수가 많다고 가정했을 때 : ~O(E * log E)이 비례한 시간 걸린다.

이 시간복잡도에는 불필요한 간선이 포함되어 있다.
MST와 나머지 정점 연결하는 간선을 선택할 때, MST 내부를 연결하는 간선도 일부 포함되었다.
따라서, MST 만드는데 불필요한 간선도 일단 PQ에 쌓아 두었다 나중에 pop할 때 검사하고 제거했다.

하지만, MST에 포함되지 않은 나머지 정점 별로 최소 weight 간선 하나씩만 포함하도록 선택하게끔 수정하여
MST에 포함된 정점에 대한 간선을 포함하지 않도록 PQ에 저장할 수 있다.

Eager한 방식

정점의 갯수만큼만 간선 저장 공간을 가지는 Indexed PQ 사용
MST에 포함되지 않은 정점 별로 최소 weight 간선 하나씩만 가진다.

Prim Eager 알고리즘의 비용
PQ 추가, 삭제 비용 : 최대 V 개까지의 간선만 저장하기 때문에, ~log V
insert, delete 횟수 : ~V
따라서 ~ O(V * log V)에 비례한 시간이 걸린다.

Prim Eager의 구현

def mstPrimEager(g):  
    def include(v):  
        included[v] = True  
        for e in g.adj[v]:  
            idx = e.other(v)  
            if included[idx] is False:  
                if pq.contains(idx):  
                    if pq.keyOf(idx) > e:  
                        pq.decreaseKey(idx, e)  
                else:  
                    pq.insert(idx, e)  
  
    edgesInMST = []  # Stores edges selected as part of the MST  
    included = [False] * g.V  # included[v] == True if v is in the MST  
    weightSum = 0  # Sum of edge weights in the MST  
    pq = IndexMinPQ(g.V)  # Build a priority queue  
    include(0)  
  
    while len(edgesInMST) < g.V - 1:  
        eKey, eIdx = pq.delMin()  
        edgesInMST.append(eKey)  
        weightSum += eKey.weight  
        include(eIdx)  
  
    return edgesInMST, weightSum

---

Summary

핵심 1.
MST : 모든 정점을 최소 간선을 이용하여 연결하는 Tree 중 간선의 가중치 합이 가장 작은 Tree

핵심 2.
MST를 구하기 위해 Greedy한 방법을 사용할 수 있는데,
이 방법은 특정 partition과 나머지 정점을 연결하는 간선 중 최소 비용을 가지는 간선을 반복해서 추가하는 방법이다.

핵심 3.
Greedy 한 방법에서 연결되지 않은 두 partition을 찾는 방법에서 효율적인 방법을 제시하는 두 알고리즘이 Kruskal 과 Prim 알고리즘이다.

핵심 4.
Kruskal 알고리즘은 두 Partition을 연결하는 간선을 선택할 때 Cycle을 형성하지 않는 조건을 검사한다.
이때, 조건을 검사하는 방법으로 DFS와 Union & Find 방식을 선택할 수 있다.
Weighted Quick Union 방식으로 Union & Find 를 사용하면 ~log V 에 비례한 시간으로 조건 검사를 할 수 있기 때문에 DFS 방식보다 효율적이다.
Kruskal 알고리즘의 시간복잡도는 ~O(E * log E) 이다.

핵심 5.
Prim 알고리즘은 두 Partition을 연결하는 간선을 선택할 때, 항상 MST를 형성한 Partition과 형성하지 않은 Partition을 연결하는 간선 중 최소 간선을 선택하는 방식이다.
이렇게 하기 위해,
MST를 형성한 정점과 외부 간선을 모두 PQ에 넣고 나중에 검사하는 방식(LAZY)을 사용할 수도 있지만
MST에 포함되지 않은 나머지 정점별로 최소 weight 간선 하나씩만 포함하게 하는 방식(EAGER)을 사용하면 더 효율적일 수 있다.
Eager Prim 알고리즘의 시간 복잡도는 ~O(V * log V) 이다.