최소신장트리(MST)

1. 최소신장트리(MST)

그래프에서 최소 비용을 구하는 문제, 두 정점 사이의 최소 비용 찾기 문제에 주로 사용됨

신장트리 : n개의 정점으로 이뤄진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이뤄진 트리

최소신장트리(MST: Minimum Spaning Tree) : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리(모든 정점을 연결하는 간선의 가중치의 합이 최소가 되는 트리)

MST의 표현 : 그래프, 간선들의 배열, 인접리스트, 부모 자식관계와 가중치 배열

2. MST 알고리즘

2-1. Prim 알고리즘

하나의 정점에서 연결된 간선들 중에 하나씩을 선택하면서 MST를 만들어 가는 방식으로 어떤 정점으로 시작해도 결과 값인 트리는 같다.

(1) 임의의 정점을 하나 선택한다.

(2) 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택

(3) 모든 정점이 선택될 때까지 (1), (2)를 반복한다.

Prim 알고리즘을 이용한 MST 구현

서로소인 두개의 집합이 필요하다.

• 트리집합 : MST를 만들기 위해 선택된 정점들
• 비트리집합 : 선택되지 않은 정점들

2-2. KRUSKAL 알고리즘

간선을 하나씩 선택해서 MST를 찾는 알고리즘, Prim보다 이해하고 구현하기 쉽다.

(1) 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬

(2) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴

• 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
• 다음 정점의 representative가 같다면 사이클이 존재한다고 볼 수 있다.

(3) n-1개의 간선이 선택될 때까지 (2)를 반복한다.

Prim보다 구현하기 쉽지만, 간선이 많은 경우 sorting과정(1)이 오래 걸린다.