최소 신장 트리

 

 

 

그래프에서 일부 간선을 선택해서 만든 트리를 신장 트리 (Spanning Tree)라고 한다.

 

트리라서 사이클이 있으면 안되니 n개의 정점이 있으면 정점을 모두 잇는 트리의 간선은 n-1개이다.

 

최소 신장 트리는 신장 트리에서 간선에 가중치가 있다고 할 때 가중치의 합이 최소인 트리를 말한다.

 

 

활용 분야는 통신, 회로 등 여러 군데가 있을 수 있고 생각해보면 더 많이 있을 것 같다..

하지만 나한테는 활용 분야보다 최소 신장 트리를 활용하는 알고리즘 문제가 나온다는거다.

 

 

 

가중치가 있는 그래프가 주어졌을 때 최소 신장 트리를 어떻게 구할 수 있을까?

 

최단 거리를 구할 때 사용하는 알고리즘인 크루스칼, 프림 알고리즘을 사용할 수 있다.

 

https://chanhuiseok.github.io/posts/algo-33/

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)

 

 

잘 설명해 준 블로그를 참고해서 공부하자.