[이산수학] 트리 - 최소 비용 생성 트리(MST)

최소 비용 생성 트리

최소 비용 생성 트리(Minimum spanning Tree : MST)란 최소한의 비용을 가지는 생성 트리를 말한다. 대표적인 예로는 통신 네트워크 연결이 있으며 각 도시들을 연결하는 데 있어 최소 비용으로 연결하는 방법을 찾는 것이다.

프림 알고리즘

프림 알고리즘은 무방향 그래프에서 사용되며 임의의 정점을 선택하고 정점으로부터 최소 간선을 선택하면서 정점을 추가해내가는 알고리즘이다. 

특징

• 시간 복잡도 :
  • 평균- O(E*logV) : 최소 힙으로 구현
  • 최악 - O(V^2) : 배열로 구현
• 모든 정점을 순회하며, 사이클이 형성되지 않아야 한다.
• 그리디 알고리즘 사용

알고리즘

1. 최초의 정점을 임의로 선택한다.
2. 정점의 간선들 중 최소 비용을 찾고, 해당 간선에 연결된 정점을 정점 집합에 추가한다.
3. 이때 이미 지나온 정점과 연결되어 있거나, 사이클이 발생하지 않는 간선을 선택해야 한다.
4. 정점 집합에서의 모든 정점에 연결된 간선들 중 최소 비용을 찾아 반복한다.

크루스칼 알고리즘

최초의 정점없이 최소 간선을 하나씩 추가하여 MST를 생성해나가는 알고리즘이다.

특징

• 시간 복잡도 : O(E*logV)
• 가중치가 최소인 간선을 하나씩 선택해 나간다.
• 간선의 가중치를 오름차순으로 정렬하는 선행이 필요하다.
• 모든 정점을 순회하며, 사이클이 형성되지 않아야 한다.
• 그리디 알고리즘 사용

알고리즘

1. 간선의 가중치를 오름차순으로 정렬한 집합을 생성한다.
2. 최소 가중치의 간선을 시작으로 정점을 순회한다.
3.  사이클이 형성될 경, 해당 간선은 건너뛴다.