Algorithm design - MST

---

신장 트리

신장 트리(spanning tree)는 무향그래프 G=(V,E)에서 V는 그대로 두고 간선을 |V|-1개만 남겨 트리가 되도록 만든 것이다. DFS,BFS에사용된 간선 집합 T는 그래프 G의 신장 트리를 의미한다. 주어진 그래프 G에 대한 신장 트리는 유일하지 않다.

---

MST

MST는 최소 비용 신장 트리(minimum cost spanning tree)의 준말이다. 신장트리가 되는 G의 부분그래프 중에서 가중치가 최소가 되는 부분그래프를 최소비용신장트리(MST, minimum spanning tree)라고 한다. 여기서 최소의 가중치를 가진 부분그래프는 반드시 트리가 되어야 한다. 왜냐하면, 만약 트리가 아니라면, 순환경로(cycle)가 있을 것이고, 그렇게 되면 순환경로 상의 하나의 이음선을 제거하면 더 작은 비용의 신장트리가 되기 때문이다.
최소 비용 신장 트리를 구하기 위한 Kruskal, Prim, Sollin과 같은 알고리즘이 존재한다.
신장 트리의 제한조건은 가중치가 부여된 무방향 그래프여야하고 n–1(n=|V|)개의 간선만 사용하고 사이클을 생성하는 간선은 사용이 금지된다는 것이다.

아래와 같은 문제들에서 유용하게 쓰일 수 있다.

도로건설 - 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제

통신(telecommunications) - 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제 

배관(plumbing) - 파이프의 총 길이가 최소가 되도록 연결하는 문제

---

Kruskal 알고리즘

Kruskal 알고리즘의 과정을 간단히 살펴보면 아래와 같다.
- 한번에 하나의 간선을 선택하여, 최소 비용 신장 트리 T에 추가
- 비용이 가장 작은 간선을 선정하되, 이미 T에 포함된 간선들과 사이클을 형성 하지 않는 간선만을 추가
- 비용이 같은 간선들은 임의의 순서로 하나씩 추가

 

핵심 구현 요소는 가중치에 따라 오름차순으로 정렬한 간선의 순차리스트를 유지하며 최소 비용 간선을 선택하도록 하는 것과 사이클 방지 검사가 있다.

---

Prim 알고리즘

Prim 알고리즘은 한번에 하나의 간선을 선택하여, 최소 비용 신장 트리 T에 추가하는 간선 중심의 알고리즘이다. Kruskal 알고리즘과는 달리 구축 전 과정을 통해 하나의 트리만을 계속 확장한다.
작동 과정을 살펴보면 아래와 같다.

- 하나의 정점 u를 트리의 정점 집합 V(T)에 추가
- V(T)의 정점들과 인접한 정점들 중 최소 비용 간선 (u,v)를 선택하여 T에 추가, 정점은 V(T)에 추가 

- T가 n-1개의 간선을 포함할 때까지, 즉 모든 정점이 V(T)에 포함될 때까지 반복
- 사이클이 형성되지 않도록 간선 (u,v)중에서 u 또는 v 하나만 T에 속하는 간선을 선택

 

두 알고리즘의 시간 복잡도를 비교하자면 아래와 같기 때문에 각각 효율적으로 쓰일 수 있는 상황이 다르다.

따라서, Sparse graph(m = n-1)인 경우 Kruskal이 우세하고 Dense graph(m = n(n-1)/2)인 경우는 Prim이 우세하다.

---