최소 신장 트리(MST)

유니온-파인드를 공부하면서 문제를 풀다 최소 신장 트리로 푸는 문제가 나와 정리해보았다.

최소 신장 트리를 알기 전에 신장 트리가 무엇인지 알아야 한다.

신장 트리(Spanning Tree)

그래프 내의 모든 정점을 포함하는 트리인데 여기서 신장 트리는 그래프의 최소 연결 부분 그래프이다. 따라서 신장 트리는 간선의 수가 가장 적으면서 그래프의 모든 정점을 포함한다.

최소 신장 트리(MST)

신장 트리 중 사용된 간선들의 가중치 합이 최소인 트리이다.

하지만 각 간선의 가중치가 동일하지 않을 때 단순히 가장 작은 간선을 선택한다고 해서 최소 비용이 얻어지는 것이 아니다.

그래프에 있는 모든 정점들을 가장 적은 수의 간선과 적은 비용으로 연결하는 것이 최소 신장 트리이다.

구현 알고리즘

Kruskal algorithm

그리디 알고리즘을 이용하여 MST를 구하는 방법이다.

MST가
1. 최소 비용의 간선으로 구성됨
2. 사이클을 포함하지 않음
의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택하여 MST를 구한다.

<과정>

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
3. 해당 간선을 현재의 MST의 집합에 추가한다.

이 때 사이클을 형성한다는 것은 유니온-파인드 알고리즘에서 같은 부모를 가진다는 의미가 되기때문에 사이클 형성 검사에 유니온-파인드 알고리즘을 이용할 수 있다.

Prim Algorithm

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법

• 정점 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법

<과정>

1. 시작 단계에서는 시작 정점만을 집합에 포함한다.
2. 앞 단계에서 만들어진 집합에 인접한 정점들 중 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
   • 비용이 가장 낮은 간선 선택
3. 집합의 크기가 n-1이 될 때까지 반복한다.