[Introduction to Algorithms] 최소 신장 트리

 

1) 최소 신장 트리란?

- 전자 회로를 설계할 때, 요소 몇 개의 핀을 전선으로 연결하여 전기적으로 등가가 되도록 

  만들어야 하는 경우가 있다.

  n개의 핀을 서로 연결하기 위해 n-1개의 전선을 사용할 수 있는데,

  여기서 전선 하나가 핀 2개를 연결한다.

  일반적으로 전선을 배치하는 모든 방법 중에서 전선을 가장 적게 사용하는 방법이 가장 바람직하다.

 

- 전선을 연결하는 문제를 연결 무방향 그래프 G = (V, E)로 모델링할 수 있다.

  이 때, V를 핀의 집합, E를 연결 가능한 핀 쌍들의 집합, w(u, v)를 각 간선(u,v) < E마다 

  u와 v를 연결하는 비용(필요한 전선의 양)을 나타내는 가중치로 둔다. 

 

- 그런 다음 모든 정점을 연결하고 전체 가중치의 합인 다음을 최소화하는 

  비순환 부분 집합 T<E를 찾는다.

 

- 여기서 T는 비순환이고, 모든 정점을 연결하므로 트리를 형성한다.

  그리고 이 트리는 그래프 G에서 신장(span)하므로 신장 트리라고 한다.

 

- 트리 T를 결정하는 문제를 최소 신장 트리 문제라고 한다.

  최소 신장 트리 문제를 해결하는 두 개의 알고리즘이 있는데,

  바로 크루스칼 알고리즘과 프림 알고리즘이다.

 

- 일반적인 이진 힙을 사용하면 각각 O(ElgV) 시간에 쉽게 실행할 수 있다.

  피보나치 힙을 사용하면 프림 알고리즘이 O(E+VlgV) 시간에 실행되어

  속도가 빨라질 수 있는데,

  |V|가 |E|보다 훨씬 작을 때, 이진 힙 구현보다 속도가 향상된다. 

 

- 두 알고리즘은 그리디 알고리즘이다.

  그리디 알고리즘의 각 단계에서는 가능한 몇 가지 선택 중 한 가지를 선택해야 한다.

  그리디 방법은 그 순간에서 가장 좋은 것을 선택한다.

 

- 이런 방법은 일반적으로 어떤 문제에 대해 언제나 최적해를 찾는 것을 보장해주지 못한다.

  하지만 최소 신장 트리 문제에서는 특정 그리디 방법을 사용하면 

  최소 가중치의 신장 트리를 얻을 수 있다는 것을 증명할 수 있다.