북북이와 렛츠기릿

최소 스패닝 트리 (Minimal Spanning Tree) - 최소한의 비용을 들어서 관계도를 만드는 것 - 주의 : 트리는 순환이 없어야 한다. - 최소 스패닝 트리를 해결하기 위한 알고리즘은 '프림 알고리즘(Prim's algorithm)'과 '크루스칼 알고리즘(Kruskal's algorithm)'이다. - 위키 사이트에 "예제"를 보면 실제 알고리즘이 어떻게 돌아가는지 파악이 쉽다. 1. 프림 알고리즘 - 정점을 선택하고, 그것과 연결되 가장 적은 비용의 정점을 선택하는 방식 - 위키 : http://ko.wikipedia.org/wiki/프림_알고리즘 2. 크루스칼 알고리즘 - 모든 비용을 순차적으로 나열하여, 가장 적은 비용이 드는 간선을 선택해 나가는 방식 - 위키 : http://ko.w..