[알고리즘] 최소 신장 트리 MST

✔️ 최소 신장 트리 (MST) 란?

무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리를 뜻함

✔️ 신장 트리란?

N개의 정점으로 이루어진 무향 그래프에서의 트리
무향 그래프 이기 때문에 N-1 개의 간선을 가짐

이러한 MST 문제를 완탐의 관점에서 보면 너무나 큰 시간의 복잡도를 가지기 때문에
완전탐색의 방법을 사용할 수 없다.

MST를 풀어내는 알고리즘 두 가지
1. 크루스칼 알고리즘
2. 프림 알고리즘

✔️ 크루스칼 알고리즘

간선을 하나씩 선택해서 MST를 찾는 알고리즘
$\to$ 간선을 하나씩 선택하기 때문에, 간선리스트로 그래프를 표현하면 된다.

유니온 파인드와 거의 코드는 유사하다.

👩🏻‍💻 과정

1. 전처리

간선을 오름차순으로 정렬한다.

2. 실행 (트리를 연결하는 과정 / 합치기)

간선을 하나씩 선택하면서, 사이클이 발생하지 않는다면 간선을 선택한다 (Union(a,b))
즉, a와 b의 대표자가 이미 같으면 union 할수 없다.

3. 기저조건

MST 는 무향 그래프이기 때문에 간선이 N-1 개이다.
즉 N-1번의 합치기가 완료되면 끝나면 됨.

크루스칼 알고리즘 시각화 자료 : 크루스탈 알고리즘 시각화 자료 유튜브 링크

✔️ 프림 알고리즘

하나의 정점에서 연결된 간선들 중에 하나씩 MST를 만들어 가는 방식
$\to$ 정점 중심이기 때문에 인접행렬 또는 인접리스트 를 선택하면 된다.

👩🏻‍💻 과정

1. 임의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
3. 모든 정점이 선택될 때 까지, 2번 과정을 반복

중요한 점은
트리 정점들과 비트리 정점들을 구분하여 정보를 유지해야한다는 점이다.

프림 알고리즘 시각화 자료 : 프림 알고리즘 시각화 자료 유튜브 링크