[알고리즘] (MST)최소 신장 트리란?

Spanning Tree(신장트리)란 무엇인가? 

 

• 그래프내의 모든 정점을 포함하는 트리를 말한다.
• 신장 트리 =  스패닝 트리 전부 같은 말이다 (아래부턴 신장트리)
• 신장 트리는 그래프의 최소 연결 부분을 찾는 그래프이다
  • 여기서 최손 연결이란 간선의 수가 가장 적은걸 뜻한다.
  • n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다.
    
    

출처 : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

Spanning Tree의 특징은?

 

• DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다.
• 탐색 도중에 사용된 간선만 모으면 만들 수 있다.
• 하나의 그래프에는 많은 신장 트리가 존재할 수 있다.
• Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.
• 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다.

 

MST 란?

• Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
• MST = Minimum Spanning Tree = 최소 신장 트리
• 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다.
• MST는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말한다.
• 즉, 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.

 

MST의 특징

• 간선의 가중치의 합이 최소여야 한다.
• n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
• 사이클이 포함되어서는 안된다.
  
  

구현방법 1 : Kruskal MST 알고리즘

• 탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것
• MST가 1) 최소 비용의 간선으로 구성됨 2) 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다.
• 간선 선택을 기반으로 하는 알고리즘이다.
• 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이다.
  
  

• 과정
  • 1. 시작단계에서는 시작 정점만이 MST 집합에 포함되게 한다
  • 2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다 
    • 가장 낮은 가중치를 먼저 선택하고 사이클을 형성하는 간선을 제외한다.
  • 3. 해당 간선을 현재의 MST 집합에 추가한다.

 

구현방법 2:  Prim MST  알고리즘

• 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법
• 장점 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장트리를 확장하는 방법

 

• 과정
  • 1. Kruskal  MST 알고리즘과 마찬가지로 시작 정점만을 MST에 포함시킨다
  • 2.  앞단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. =  Kruskal  MST 와 마찬가지로 가중치가 가장 작은 정점을 선택한다
  • 3. 위 과정을 통해 트리가 N-1개의 간선을 가질때 까지 반복한다.

 

 

참고 블로그 : https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

참고영상 :https://youtu.be/LQ3JHknGy8c