자료구조 - MST 학습

MST(Minimum cost Spanning Tree)

신장 트리(Spanning Tree)

1. connected(연결되어 있다.)
2. 최소 엣지 수 |E| = |V| - 1 (트리 조건)
3. E(G’)는 E(G)에 포함되어 있다.
4. V(G’) = V(G)

최소 비용 신장 트리

1. 무방향 그래프
2. 가중치 그래프
3. 비용(cost) 최소화

MST 알고리즘

탐욕 알고리즘(Greedy algorithm)

1. Kruskal algorithm
2. Prim algorithm
3. Sollin algorithm

• 전역적 최적해(global optimum)를 찾기 위해 각 스테이지마다 지역적 최적해(local optimum)를 선택(지역적 최적 선택의 모음이므로 전역적으로 최적해라는 보장이 없다.)

탐욕 알고리즘이 실패하는 예시

탐욕 알고리즘이 성공하기 위한 조건

1. Greedy choice property : 지역 최적해를 선택해 나가면 전역 최적해에 도달할 수 있다.
2. Optimal substructure : 문제에 대한 최적해가 부분 문제에 대한 최적해를 포함할 때

Greedy MST algorithm

단순화 가정

• Edge 가중치는 서로 다르다(distinct)
• 그래프는 연결되어 있다.(connected)
  결과
• 최소 비용 신장 트리가 존재하며 유일하다.(unique)

컷(Cut)