[알고리즘] 최소 신장 트리(MST:Minimum Spanning Tree)란?

기존 그래프는 정점의 집합과 간선의 집합으로 이루어진 자료구조이다.

여기서 새로운 속성인 간선간의 가중치(Weight)를 부여해주게 된다.

 

 

최소 신장트리에서 신장트리(Spanning Tree)에서 Spanning는 여러 가지 뜻을 갖고 있지만, 떨어져 있는 둘 사이를 다리 등으로 연결한다는 뜻으로 사용. 즉, 신장 트리는 그래프의 모든 정점을 연결하는 트리이다.

 

신장트리는 한편으로 그래프의 하위 개념이기도 합니다. 그래프는 사이클을 형성하는 간선만 제고하면 트리로 됩니다.

 

최소 신장트리란 결국 최소 가중치 신장트리라고도 불립니다. 각 간선이 갖고 있는 가중치의 합이 최소가 되는 신장 트리가 바로 최소 신장 트리인것이다.

 

 

보통 "최소한의 비용으로 모든 도시를 연결하는 도로를 건설할 방법을 찾아라"라는 문제가 주어졌을때의 좋은 해결도구이고, 최소 신장 트리 알고리즘에 일반적으로 사용되는 알고리즘은 프림 알고리즘과 크루스칼 알고리즘이다.

 

 

hyo-ue4study.tistory.com/146?category=951082

[알고리즘]프림 알고리즘(Prim'a Algorithm)

 

 

hyo-ue4study.tistory.com/145?category=951082

[알고리즘]크루스칼 알고리즘(Kruskal's Algorithm)