MST

MST에 들어가기에 앞서 기본 배경들

1. Tree: 한 그래프 내에 모든 노드들이 연결되어있고(connected) 사이클이 없는(acyclic) 무방향(undirected) 그래프를 의미. 

2. Forest: 사이클이 없는 무방향 그래프로 한 그래프에 1개 이상의 tree들이 존재

3. Spanning Tree 신장트리

    - 그래프 내에 모든 정점을 포함하는 트리로 그래프의 최소 연결(간선) 부분 그래프이다.

 

최소 연결이란 간선의 수가 가장 적다는 뜻

n개의 정점을 가지면 m이 간선이 수일 경우 m = n-1 ->그래프에서 일부 간선을 선택해서 만든 트리

DFS와 BFS에서 탐색 도중 사용된 간선들과 모든 노드를 합쳐 spanning tree만듬.

---

Minimum Spanning Tree 최소신장트리

- Spanning tree 중 사용된 간선들(n-1개)의 가중치 합이 최소인 트리

  즉, 그래프 내에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 트리

 

- MST 구현 알고리즘 2개 -> greedy algorithm 사용

  1. Prim’s algorithm

: 시작 정점에서부터 출발하여 MST를 확대해가는 방식

 (정점 선택 방식, 이전 단계에서 만들어진 신장트리를 확장하는 방법)

 Vertex를 3개의 상태로 나눈다.

1) Tree vertex : MST에 속한 vertex

2) fringe vertex : tree vertex의 후보

3) Unseen vertex : Tree, fringe를 제외한 나머지 vertex

구현 순서

(1)   시작 단계에서는 시작 정점(starting vertex)만이 MST(최소 비용 신장 트리) 집합에 포함된다.

     (시작 정점은 임의로 결정)

(2)   앞 단계에서 만들어진 MST 집합에 인접한 정점들(Fringe vertex) 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.

(가장 낮은 가중치를 먼저 선택한다.) -> greedy

(3)   앞의 과정을 트리가 N-1개의 간선을 가질 때까지 반복한다.

 

        -> 알고리즘이 종료됐을 때 만들어진 트리가 MST

  2. Kruskal’s algorithm

: 가중치가 작은 간선부터 선택하여 MST를 구한다.

(간선 선택 방식, 이전 단계에서 만들어진 신장 트리랑 상관없이 무조건 최소 간선만 선택)

 구현 순서

(1)   그래프의 간선들을 가중치의 오름차순으로 정렬한다.

(2)   정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.

즉, 가장 낮은 가중치를 먼저 선택한다. ->greedy

사이클을 형성하는 간선을 제외.

(3)   해당 간선의 두 정점이 연결되어 있지 않다면 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다.

 

 사이클 생성하는지 확인하고, 안 생성할 경우 정점을 연결하는 작업은

 Union-find 연산을 이용

+Union-find 연산 : Kruskal 알고리즘 말고도 널리 사용되는 연산

  - Union(u,v) : 원소 u와 v가 속해있는 집합을 입력받아, 두 집합을 합쳐주는 연산

  - Find(u) : 원소 u가 속해있는 집합을 반환해주는 연산