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

Minimum Spanning Tree

* 그래프에서 최소 비용 문제

 1. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 -> 최소 신장 트리

 2. 두 정점 사이의 최소 비용의 경로 찾기

 

* 신장 트리

 - n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

 

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

 - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리

 

* MST의 특징

1. 사이클이 포함되어서는 안된다.
2. 간선의 가중치의 합이 최소여야 한다. -> MST의 정의

 

* 현실에서의 MST

현실에서의 예를 들자면 케이블 회사가 클라이언트를 모두 연결하면서 케이블을 연결하는 비용을 최소로 하고 싶을 때 등이 있다. 

 

MST의 알고리즘에는 KRUSKAL과 PRIM이 있다.

 

참고 - https://www.statisticshowto.com/minimum-spanning-tree/#:~:text=A%20minimum%20spanning%20tree%20is,path%20joins%20any%20two%20vertices.

Minimum Spanning Tree: Definition, Examples, Prim's Algorithm - Statistics How To