[Algorithm] (Java) MST - 크루스칼, 프림 알고리즘

MST(Minimum Spanning Tree) 최소 신장 트리

그래프의 모든 정점을 사이클 없이 잇는 (신장 트리) 트리에서 간선의 가중치의 합이 최소가 되는 트리를 말한다.

 

크루스칼 알고리즘

• 간선 중심으로 최소 신장 트리를 구하는 알고리즘.
• 간선이 적을때 프림 알고리즘보다 유리하다.
• 내부적으로 union-find 알고리즘을 사용

 

1. 간선들을 가중치의 오름차순 정렬하여 가장 작은 간선을 선택한다.
2. 그 간선이 지금까지 만들어진 MST와 싸이클을 형성한다면 제외하고 아니라면 MST에 추가한다.
3. 모든 간선에 대해 반복한다.

 

 

프림 알고리즘

• 정점 중심으로 최소 신장 트리를 구하는 알고리즘
• 정점이 적을때 크루스칼 알고리즘보다 유리

 

1. 임의의 정점 선택
2. 그 정점과 인접한 정점을 잇는 간선 중 가중치가 가장 낮은 간선 선택
3. 그 간선이 연결하는 정점 선택, 모든 정점에 대해 2번 과정 반복

 

 

---

출처

[알고리즘] 자바 최소 신장 트리(MST) 구하기 - 크루스칼, 프림 알고리즘 (백준 1197)