JUINTINATION

최소 신장 트리(MST)란? 가중치 그래프에서 사이클 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 즉, 어떤 가중치 그래프의 신장 트리 중 선분들의 가중치 합이 최소인 트리 신장 트리는 그래프에서 사이클 없이 모든 점들을 연결시킨 트리로 주어진 그래프의 신장 트리를 찾으려면 사이클이 없도록 모든 점을 연결시키면 된다. 신장 트리는 그래프에서 사이클 없이 모든 점들을 연결시킨 트리로 그래프의 점이 n개 있다면 신장 트리에는 n-1개의 선분이 있다. 다음 예시에서 왼쪽 그림의 그래프의 최소 신장 트리는 오른쪽 그림의 그래프와 같다. MST를 찾기 위한 알고리즘 최소 신장 트리를 찾는 대표적인 그리디 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리..