Spanning Tree : 모든 vertex를 연결한 트리
Minimum Spanning Tree(=Minimum Weight Spanning Tree) : 각 vertex사이의 weight 합이 최소가 되는 Spanning Tree
- vertex간의 weight란? edge에 적혀있는 값을 말함 (가중치라고도 부름)
Minimum Spanning Tree를 만들기 위한 조건 : spanning tree이어야하고 각 edge에서 weight가 있어야 한다. (Connected Weighted Graph)
MST는 어디에 쓸까?
- 지도상에서 도시간 최소 거리 찾기
MST를 만드는 알고리즘
- Prim's Algorithm : vertex에서 주변 정보를 파악하면서 MST를 구축
- Kruskal's Algorithm : 모든 edge의 weight 정보를 알고있다는 가정하에 MST를 구축
댓글 없음:
댓글 쓰기