최소신장트리(MST) 알고리즘 (Prim, Kruskal)

먼저, 신장트리(Spanning Tree)란 방향성이 없는 N개 정점의 가중치 그래프에서 모든 정점을 연결하는 N-1개의 간선으로 구성된 트리를 말한다. 즉, 최소신장트리(MST: Minimum Spanning Tree)는 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 신장트리를 찾는 것이다. MST를 구할 때 대표적으로 쓰이는 프림(Prim), 크루스칼(Kruskal) 알고리즘에 대해 알아보자.

 

 

프림(Prim)

: 정점을 선택/미선택 집합으로 구별하고, 선택된 정점 <-> 미선택된 정점 사이의 간선 중 가장 작은 간선을 택하면서 정점을 연결해나가는 방법의 풀이이다. => 정점 중심 풀이

 

[풀이 순서]  

 1. 임의의 정점을 하나 선택.

 2. 선택된 정점들로부터 인접한 아직 선택되지 않은 정점까지의 가장 가중치가 적은 간선을 선택

 3. 모든 정점이 선택되었으면 완료.

 

Prim 풀이

 

크루스칼(Kruskal)

: 가장 가중치가 작은 간선부터 하나씩 선택하며 정점을 연결하는 방법의 풀이이다. 단, 최소스패닝트리 경로에는 사이클이 발생하면 안되기 때문에 간선을 선택할 때 Union-Find 알고리즘을 적용하여 사이클 발생여부를 확인한다. => 간선 중심 풀이

 

[풀이 순서]

 1. 모든 간선을 가중치 크기가 작은 순으로 정렬하여 선택.

 2. 선택할 간선과 연결된 두 정점이 이미 연결되어있는지 확인 (Union-Find)

 3. 더이상 선택할 간선이 없으면 완료

 

Kruskal 풀이

 

 

각각 Python 구현 코드는 아래 연습문제 풀이 게시글에서 볼 수 있다.

[연습문제] 2021.07.18 - [Algorithm/문제풀이] - [Python][백준] 1197_최소 스패닝 트리(Prim, Kruskal)