Overview

Minimum Spanning Tree(최소 신장 트리)를 만드는 알고리즘은 대표적으로 두 가지가 있는데, 모두 Greedy Algorithm이다. MST를 통해 도로, 배수관, 통신망 등 분야에서 최소 비용으로 최대 효율을 낼 수 있다.

Spanning Tree

Spanning Tree(신장 트리) $T(V’, E’)$는 그래프 $G(V,E)$ 내의 모든 vertices를 가지는 최소 연결 부분 그래프이다.

• G의 부분 그래프이므로 $V’ \subset V$, $E’\subset E$이다.
• 모든 vertices를 가지기 때문에 V’ = V이다.
• 트리 구조이기 때문에 cycle이 없다.
• $\frac {|V|} 2 ≤ |E| < |V|^2$
• $|E’| = |V|-1$

Minimum Spanning Tree

Minimum Spanning Tree(최소 신장 트리)는 weighted edge의 합이 최소가 되는 트리 구조이다.

• edge는 가중치를 가진다.

과정

• cycle을 만들지 않는 선에서 가중치가 낮은 edge를 추가해 나간다. (greedy)
• $|V|-1$회 반복한다.

Prim’s Algorithm

Prim’s Algorithm(프림 알고리즘)은 트리를 점진적으로 구축하는 방법으로, 사이클이 생성되지 않는 선에서 Spanning Tree와 연결되어 있고 가중치가 낮은 edge를 선택하여 트리에 추가하는 방법이다.

과정

1. 그래프에서 임의로 하나의 vertex을 선택하여 트리를 만든다.
2. 가중치가 가장 낮은 edge로 연결된 vertex $\notin V’$를 선택한다. (greedy)