06-4 신장 트리와 최소 비용 신장 트리

※ 신장트리(Spanning Tree)

 - 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리

 - 연결 그래프에서 순회를 하면 n-1개의 간선을 이동하면서 모든 정점을 방문하게 되므로 신장 트리를 생성하게 된다. 

   너비 우선 탐색을 이용하여 생성된 신장 트리를 너비 우선 신장트리, 깊이 우선 탐색을 이용해 생성된 깊이 우선 신장 트리라고 한다.

 - 신장 트리는 최소의 간선을 이용하여 모든 정점을 연결한 그래프가 된다.

   이러한 신장트리는 최소의 도로를 이용한 도로망 건설이나 최소의 네트워크선을 이용하여야 하는 통신망 설계 등에 응용된다.

※ Kruskal 알고리즘1

 - 가중치가 높은 간선을 내림차순으로 정렬하여 연결이 끊기지 않도록 하면서 가중치가 가장 높은 간선을 하나씩 삭제해 나간다.

   그렇게 최소한의 간선만 남기고 모두 지워지게 되어 최소 비용 신장 트리가 완성된다.

※ Kruskal 알고리즘2 

 - 가중치가 가장 작은 간선을 오름차순으로 정리하여 가장 작은 가중치의 간선들로 순서대로 하나씩 연결하면서 최소한의 간선을

   생성하여 최소 비용 신장 트리를 완성 시킨다. 

※ Prime 알고리즘

 - 간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해 나가는 방법이다. 한 정점에서 시작하여 트리를 확장해 나갈 때

   그 정점에 간선이 여러개 있다면 최소 가중치를 연결하고 이런 방식으로 모든 간선들을 연결해 나간다.