[CS Study] 알고리즘 (2) - 최소 신장 트리

시작하기 전에

두 번째 챕터는 최소 신장 트리입니다.

신장 트리란, 그래프의 모든 정점을 포함하는 트리를 의미합니다. 그 중에서 최소 신장 트리(MST, Minimum Spanning Tree)는 가중치가 있는 그래프에서 간선의 가중치 총합이 가장 작은 신장 트리를 의미합니다.

최소 신장 트리를 생성하는 '프림 알고리즘'과 '크루스칼 알고리즘'의 작동 원리를 이해해봅시다.

공부하는 데 많은 도움을 받은 '기술면접대비 CS전공 핵심요약집' 저자분께 감사드립니다.

프림 알고리즘이란?

프림 알고리즘(Prim algorithm)은 그리디 알고리즘으로, 임의의 정점을 시작점으로 트리를 확장하면서 최소 신장 트리를 생성하는 방식이다. 현재 트리에 포함된 정점과 연결된 간선 중 가중치가 가장 작은 간선으로 연결된 정점을 선택하는 과정을 반복하며 모든 정점이 포함될 때까지 트리를 확장한다.

크루스칼 알고리즘이란?

크루스칼 알고리즘(Kruskal algorithm)도 그리디 알고리즘이며, 간선을 오름차순으로 정렬한 뒤 가중치가 낮은 간선을 선택하면서 최소 신장 트리를 생성하는 방식이다.

만약 특정 간선을 선택했을 때 사이클이 생성된다면 해당 간선은 선택하지 않고 다음으로 가중치가 낮은 간선을 확인한다. 아랭 예시에서, 6과 3 사이의 18을 선택해야 하는 순간에 [1, 6, 3, 2] 사이클이 생성되어 버리니 18을 선택하지 않고 그 다음 22를 선택하는 모습을 확인할 수 있다.