[알고리즘] 스패닝 트리, 최소 스패닝 트리 (Spanning Tree, MST:Minimum Spanning Tree)

Spanning Tree란, 그래프 내의 모든 정점을 포함하는 트리

Spanning Tree는 그래프의 최소 연결 부분 그래프 이다.
최소 연결 = 간선의 수가 가장 적다.
n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다.

특징 : 

DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. (사이클 포함x, 모든 정점 방문o)
탐색 도중에 사용된 간선만 모으면 만들 수 있다. (n-1개의 간선으로 형성)
하나의 그래프에는 많은 신장 트리가 존재할 수 있다.

Minimum Spanning Tree란, 위에서 정의한 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리(간선의 가중치 고려)

특징:

모든 간선들의 가중치 합이 최소이다.

 

 

크루스칼 알고리즘(Kruskal MST)

• greedy 방식의 해법(이전 단계에서 만들어진 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법.)

Process
1, 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2, 정렬된 간선 리스트에서 순서대로(가장 낮은 가중치) 간선을 선택한다.
3, 사이클을 형성하는지 확인, 사이클이면 해당 간선을 제외한다.
4, 제외되지 않았다면, 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.

프림 알고리즘(Prim MST)

• 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장

Process

1, 먼저 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다.
2, 집합에서, 인접한 정점들 중 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
3, 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.