그래프에서 일부 간선을 선택해서 만든 트리를 신장 트리 (Spanning Tree)라고 한다.
트리라서 사이클이 있으면 안되니 n개의 정점이 있으면 정점을 모두 잇는 트리의 간선은 n-1개이다.
최소 신장 트리는 신장 트리에서 간선에 가중치가 있다고 할 때 가중치의 합이 최소인 트리를 말한다.
활용 분야는 통신, 회로 등 여러 군데가 있을 수 있고 생각해보면 더 많이 있을 것 같다..
하지만 나한테는 활용 분야보다 최소 신장 트리를 활용하는 알고리즘 문제가 나온다는거다.
가중치가 있는 그래프가 주어졌을 때 최소 신장 트리를 어떻게 구할 수 있을까?
최단 거리를 구할 때 사용하는 알고리즘인 크루스칼, 프림 알고리즘을 사용할 수 있다.
https://chanhuiseok.github.io/posts/algo-33/
알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)
##
chanhuiseok.github.io
잘 설명해 준 블로그를 참고해서 공부하자.