최소 신장트리(MST, Minimum Spanning Tree) - KRUSKAL 알고리즘, PRIM 알고리즘

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. 최소 신장트리(MST, Minimum Spanning Tree) - KRUSKAL 알고리즘

1) 그래프에서 최소 비용 문제

- 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리

- 두 정점 사이의 최소 비용의 경로 찾기

 

2) 신장트리

- n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

 

3) 최소 신장 트리(MST, Minimum Spanning Tree)

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

 

2. KRUSKAL 알고리즘

- 간선을 하나씩 선택에서 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘

 

1) 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬

2) 가중치가 낮은 간선부터 선택하면서 트리를 증가시킴

- 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택

- 여기서 사이클은 그래프의 정점에 연결된 간선들을 연결했을 때 루프가 도는 모양을 말함

3) n-1개의 간선이 선택될 때까지 2번을 반복한다.

 

3. PRIM 알고리즘

1) 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 최소 신장 트리(MST, Minimum Spanning Tree)를 만들어 가는 방식

- 임의 정점을 하나 선택해서 시작 - 1

- 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 - 2

- 모든 정점이 선택될 때까지 1과 2를 반복

 

2) 서로소인 2개의 집합(2 Disjoint Set) 정보를 유지

- 트리 정점 - MST를 만들기 위해 선택된 정점

- 비트리 정점 - 선택 되지 않은 정점들