최소 신장 트리 (MST)

정의

최소 신장 트리는 연결된 가중치 그래프에서 사이클 없이 모든 정점을 잇는 트리다.

이 중 간선 가중치 합이 가장 작은 신장 트리를 최소 신장 트리라 한다.

정점이 n개면 간선은 n-1개다. 하나라도 많으면 사이클이 생기고 적으면 연결되지 않는다.

그래프 예시

가상의 4개 도시 그래프로 확인한다. 간선은 A-B, A-D, B-C, B-D, C-D 다섯 개다.

각 간선에는 공사비 같은 비용인 가중치가 붙는다.

이제 가중치가 가장 작은 간선부터 골라 트리를 만들어 보자.

크루스칼 적용

간선을 가중치 오름차순으로 정렬한 뒤 하나씩 검사한다.

C-D, A-B, A-D는 서로 다른 집합이라 채택한다. 간선이 3개면 정점 4개가 모두 연결된다.

B-C와 B-D는 이미 같은 집합이라 사이클이 생기므로 버린다.

채택한 가중치 합은 1+2+3=6이다.

크루스칼과 프림 비교

두 알고리즘은 같은 MST를 구하지만 간선을 고르는 기준과 자료구조가 다르다.

크루스칼은 간선 정렬이 비용을 좌우하므로 간선 수가 적은 희소 그래프에 유리하다.

프림은 정점마다 인접 간선을 확인하므로 간선이 많은 밀집 그래프에 유리하다.

정답은 크루스칼이다. 간선 정렬이 비용을 좌우하므로 간선 수가 적을 때 유리하다.

헷갈리는 점

헷갈리기 쉬운 점은 세 가지다. 사이클 검사, 프림의 선택 기준, MST와 최단 경로의 차이다.

프림은 트리와 연결된 간선 중 가장 가벼운 것을 고른다. 정점 가중치로 착각하지 않는다.

MST는 전체 가중치 합 최소화가 목적이므로 다익스트라 최단 경로와 구분한다.

정리

MST는 사이클 없이 모든 정점을 최소 가중치로 잇는 트리다.

그래프 밀도를 보고 크루스칼과 프림 중 하나를 고른다. 희소는 크루스칼, 밀집은 프림이다.