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

최소 비용 신장 트리를 알아보기 전

신장트리(Spanning Tree)란 무엇인지 먼저 알아보자.

 

 

Spaanning Tree란 그래프 내의 모든 정점을 포함하는 트리를 말한다.

단, 트리를 연결하는 간선의 수가 최소로 이루어져야한다.

- 그래프에서 일부 간선을 선택해서 만든 트리

- n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)

 

 

 

• DFS와 BFS를 이용해 그래프에서 신장 트리를 찾을 수 있다.

• 다음 그림처럼 하나의 그래프에는 여러개의 신장트리가 존재할 수 있다.

• 모든 정점이 연결되있어야 하고 사이클이 포함되면 안된다.

 

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

 

위에서 알아본 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리를 말한다.

즉, 간선의 가중치를 고려해 최소 비용을 찾아야 한다.

 

 

이러한 MST를 구현하는 방법은 여러가지가 있는데 그 중 Kruskal MST와 Prim MST알고리즘이 있다.

 

1. Kruskal MST Algorithm

 

Greedy Algorithm 방식을 이용해 MST를 구현한다.

- 그래프의 모든 간선들을 가중치의 오름차순으로 정렬한다.

- 정렬된 간선에서 순서대로 사이클을 형성하지 않는 간선을 뽑는다.

* 정렬이 오름차순으로 되어있으므로 낮은 가중치부터 뽑게 되는 것이다.

- 뽑은 간선을 MST 집합에 추가한다.

 

2. Prim MST Algorithm

 

하나의 정점을 시작으로 잡고 단계적으로 확장해 나가는 방식이다.

- 시작 정점을 선택해 MST 집합에 추가한다.

- 앞 단계에서 추가된 정점과 인접한 정점 중 가중치가 최소인 간선을 가진 정점을 선택해 트리를 확장한다.

- 위와 같은 과정을 간선이 n-1개 될 때까지 반복한다.