[4주차] 최소 스패닝 트리

최소 스패닝 트리 (Minimal Spanning Tree)

 - 최소한의 비용을 들어서 관계도를 만드는 것

 - 주의 : 트리는 순환이 없어야 한다.

 - 최소 스패닝 트리를 해결하기 위한 알고리즘은 '프림 알고리즘(Prim's algorithm)'과 '크루스칼 알고리즘(Kruskal's algorithm)'이다.

 - 위키 사이트에 "예제"를 보면 실제 알고리즘이 어떻게 돌아가는지 파악이 쉽다.

1. 프림 알고리즘

 - 정점을 선택하고, 그것과 연결되 가장 적은 비용의 정점을 선택하는 방식

 - 위키 : http://ko.wikipedia.org/wiki/프림_알고리즘

2. 크루스칼 알고리즘

 - 모든 비용을 순차적으로 나열하여, 가장 적은 비용이 드는 간선을 선택해 나가는 방식

 - 위키 : http://ko.wikipedia.org/wiki/크러스컬_알고리즘

※샘플 문제 : https://www.acmicpc.net/problem/1197