hellogaon

최소 스패닝 트리(Minimum Spanning Tree)는 무향그래프(Undirected Graph)에서간선마다 비용이 주어질 때 그 간선들의 비용의 합이 최소인 스패닝 트리입니다.이 때 여기서 스패닝 트리는 그래프의 정점 전부와 간선의 부분 집합으로구성된 부분 그래프 중 간선들이 사이클을 이루지 않는 트리를 말합니다. 그러므로 V개의 정점을 가지고 있는 그래프의 스패닝 트리는 모든 정점이 연결되어 있고정확히 V-1개의 간선으로 연결되어 있어야 합니다.이를 구하는 두가지 알고리즘이 있으며 아래와 같습니다. 1. 크루스칼 알고리즘2. 프림 알고리즘 두 알고리즘은 모두 각 단계마다 지금 가장 좋은 방법인 비용이 최소로 드는 방법으로 이동하는앞서 배운 탐욕법을 사용하여 최소 스패닝 트리를 구하게 됩니다.크루..