[바미] 최소 신장 트리(MST, Minimum Spanning Tree)란

안녕하세요. 오늘은 최소 신장 트리에 대해 알아보도록 하겠습니다.

Spanning Tree란?

그래프 내의 모든 정점을 포함하는 트리를 말합니다.

• Spanning Tree = 신장 트리 = 스패닝 트리입니다.
• Spanning Tree는 그래프의 최소 연결 부분 그래프입니다.
  • 최소 연결 = 간선의 수가 가장 적습니다.
  • n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 됩니다.
• 그러므로, 그래프에서 일부 간선을 선택해서 만든 트리가 되죠.
  

Spanning Tree의 특징

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

Spanning Tree의 사용 사례

통신 네트워크 구축이 그 예입니다.

예를 들어, 회사 내의 모든 전화기를 가장 적은 수의 케이블을 사용하여 연결하고자 하는 경우 n개의 위치를 연결하는 통신 네트워크를 최소의 링크(간선)를 이용하여 구축하고자 하는 경우, 최소 링크의 수는 (n-1)개가 되고, 따라서 Spanning Tree가 가능해지게 되죠.

 

MST

MST란?

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

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

MST의 특징

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

MST의 사용 사례

통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우로 많이 사용 됩니다.

각 분야 별로 어떻게 사용 되는지 알아보면

• 도로 건설
  • 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제에 사용됩니다.
• 전기 회로
  
  • 단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제에 사용됩니다.
• 통신
  
  • 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제에 사용됩니다.
• 배관
  
  • 파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 연결하는 문제에 사용됩니다.

MST의 구현 방법

1. Kruskal MST 알고리즘

탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것을 말합니다.

• MST(최소 비용 신장 트리)
  • 최소 비용의 간선으로 구성됩니다.
  • 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택합니다.
• 간선 선택을 기반으로 하는 알고리즘 입니다. 그렇기 때문에이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이죠.

 

[과정]

1. 그래프의 간선들을 가중치의 오름차순으로 정렬합니다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택합니다. (즉, 가장 낮은 가중치를 먼저 선택한다.)
3. 사이클을 형성하는 간선을 제외합니다.
4. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가해줍니다.

구체적인 내용은 Kruskal MST 알고리즘이란 참고하시면 되겠습니다.

2. Prim MST 알고리즘

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법입니다.

• 정점 선택을 기반으로 하는 알고리즘입니다.
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법이다.

[과정]

1. 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함됩니다.
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장합니다.
   즉, 가장 낮은 가중치를 먼저 선택하죠.
3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복해줍니다.

구체적인 내용은 Prim MST 알고리즘이란 참고하시면 됩니다.

MST 관련 문제

최소 스패닝 트리-백준1197번
네트워크 연결-백준1922번

관련된 Post

• 자료구조 그래프(Graph)에 대해 알고 싶으시면 그래프(Graph)란을 참고하시기 바랍니다.
• 자료구조 트리(Tree)에 대해 알고 싶으시면 트리(Tree)란을 참고하시기 바랍니다.
• Kruskal MST 알고리즘에 대해 알고 싶으시면 Kruskal 알고리즘이란을 참고하시기 바랍니다.
• Prim MST 알고리즘에 대해 알고 싶으시면 Prim 알고리즘이란을 참고하시기 바랍니다.

References

C언어로 쉽게 풀어 쓴 자료구조.
https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html