[CLRS] [21-1] Minimum Spanning Tree(MST)

1. Spanning Tree(신장 트리)?

- 그래프 내의 모든 정점을 포함하는 트리

- Spanning Tree는 그래프의 최소 연결 부분 그래프이다.

 

--> 최소 연결 == 간선의 수가 가장 적다.(싸이클이 존재하지 않는다.)

--> n개의 정점을 가지는 그래프의 최소 edge의 수는 (n-1)개가 되는데,

--> 이말은 즉, (n-1)개의 edge으로 연결되어 있으면 Spanning Tree

 

2. Spanning Tree의 특징

- DFS, BFS을 이용하여 그래프에서 Spanning Tree을 찾을 수 있다.

--> 탐색 도중에 사용된 간선만 모으면 그게 Spanning Tree가 된다.

-  이러한 Spanning Tree는 하나의 그래프에서 다수로 존재 가능하다.

 

3. MST(Minimum Spanning Tree)?

- Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 Tree를 의미한다.

 

4. MST의 특징

- 1) 간선의 가중치의 합이 최소여야 함

- 2) n개의 Node를 가진 Graph에 대해 반드시 n-1개의 간선만 사용해야한다.

- 3) 사이클 포함되어선 안됨

 

 

- 22-2,22-3에서 이러한 MST를 구하는 알고리즘에 대해서 알아보자.