[Algorithm] MST(Minimum Spanning Tree)

MST 란?

• Minimum Spanning Tree 최소 신장 트리이다.
  
  
• 간선의 가중치를 고려 하여 최소 Spanning Tree 를 만든다.
  
  
• 싸이클이 없는 연결된 무방향 그래프를 트리 라고 한다.
  
  
• 모든 정점들이 연결이 되어 있어야 된다.
  
  
• 가중치의 합이 최소가 되어야 한다.
• 해가 유일하진 않다.
  - 최소 비용을 찾는 트리이기 때문에 동일한 가중치의 간선이 있을경우 해가 여러개가 될수 있다.
  
  
• Kruskal 알고리즘, Prim 알고리즘 이 있다.
  
  
• MST를 들어가기전에 Spanning Tree 를 알고가야한다.

 

 

 

 

Spanning Tree

• 신장트리라고 한다.
• 그래프의 모든 정점을 가지는 트리이다.

 

 

 

특징

• 트리의 특징은 모두 포함된다.
• 하나의 그래프는 여러 Spanning Tree 를 가질 수 있다.

 

 

그림설명

https://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm

 

 

 

 

MST 의 구조 및 생성 방법

N 개의 도시가 있고 도시를 연결 하는 방법은 다양하다.

최소 비용으로 도시들을 연결하고 싶다 이럴때 MST 알고리즘을 쓰면된다.

 

MST 를 만드는 순서는 다음과 같다.

• 1. A 집합을 만든다 
• 2. 가중치가 적은 Edge을 찾는다.
• 3. 찾은 Edge를 A에 추가 했을때 Cycle이 생기는 지 판단한다 .
• 4. Cycle이 생기는 경우 패스한다. 

 

 

 

완성된 MST

 

 

 

 

MST 알고리즘

 

순서

• 1.처음에는 A  집합을 만든다.
• 2. A = 0 이다. 공집합이다.
• 3. 집합 A에 대해서 안전한 에지를 하나 찾은후 A에 더 한다.
• 4. 에지의 개수가 n-1 개가 될때 까지 3번을 반복한다.

 

 

 

안전한 Edge 란?

A 에  (U,V) 를 추가 했을때  A 가 어떤 MST의 부분 집합이 될 경우 (U,V) 는 A에 대해서 안전하다고 한다.

 

 

 

 

안전한 Edge 찾기

• Cut: 그래프의 정점들을 2개의 집합 S 와 S를 제외한 나머지(V-S) 를 CUT 이라고 한다.
• Corss: (U,V)가 있을때  U 는 S 집합에 속하고,  V 가 V-S 집합에 속했을때 Cross 라고 한다.
• Respect: Cross 하지 않을때 존중 한다고 한다.
• Cross 되는 것 또는 Respect 엣지는 안전하다고 한다.

 

 

 

 

 

Kruskal 알고리즘

https://vprog1215.tistory.com/158

[Algorithm] Kruskal

 

 

Prim 알고리즘

 

https://vprog1215.tistory.com/206

[Algorithm] Prim