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

Spanning Tree, 신장트리란?

그래프에 포함된 모든 정점(vertex)들을 포함하는 부분 그래프이다. (즉, 그래프 구성 edge만이 달라짐)

• 모든 vertex는 적어도 하나의 edge에 연결되어 있다.
• 트리이므로 cycle이 존재해서는 안 된다.
• 주어진 하나의 그래프에 대해 다양한 신장트리가 존재할 수 있다.
• vertex의 개수 v에 대해 (v-1)개의 edge를 가진다.

신장 트리는 DFS, BFS 등을 이용하여 구성할 수 있다. (탐색을 통해 방문한 정점 순서대로 신장 트리 구성)

 

Minimum Spanning Tree, 최소 비용 신장트리

가중치가 부여된 무방향 그래프에서, 신장 트리의 비용이 가장 적은 spanning tree를 최소 비용 신장트리라 한다.

즉, 신장트리를 구성하는 edge들의 가중치(비용)의 합이 가장 적은 신장트리이다.

 

MST 구현 알고리즘

모두 Greedy method를 사용한다.

Kruskal Algorithm

한 번에 하나의 edge씩 추가하면서 MST를 생성한다. (edge 선택을 기반으로 한다.)

- 전체 edge 중에서 가장 비용이 적은 edge를 선택한다. 사이틀 형성 유무를 확인하고, 형성하지 않을 경우 포함시킨다. 

- 이전에 만들어진 신장 트리와는 관계 없이, 남은 edge 중 가장 비용이 적은 edge를 선택하여 트리를 구성

 

관련 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

 

Prim Algorithm

단 하나의 vertex만 갖는 트리에서 시작하여, 트리를 확장하여 MST를 구성한다. (vertex 선택을 기반으로 한다.)

- 현재 트리를 구성하는 정점들과 연결된 다른 정점들 중, 연결 비용이 최소인 vertex를 선택하여 트리에 포함시킨다.

- 이전에 만들어진 신장 트리 정점을 확인 -> 다른 정점들과의 비용을 바탕으로 트리를 확장