포스테키안

2021 여름호 / 지식더하기 ②

2021-07-20 53

최소 신장 트리
Minimal Spanning Tree

 

여러분, 여러 도시가 있을 때 최소의 비용으로 모든 도시가 연결되도록 하려면 어떻게 해야 할까요? 물론 도시 사이에 도로를 모두 설치하면 도시들이 모두 연결되겠지만, 한정된 예산 안에서 도로를 설치하기 위해서는 최적의 방안을 생각해내야 합니다. 이때 이용하는 것이 바로 ‘최소 신장 트리(Minimal Spanning Tree)’입니다. 다소 낯선 이름의 최소 신장 트리, 기초적인 것부터 하나하나 함께 알아볼까요?
우선, 신장 트리가 무엇인지부터 알아봅시다. 그래프는 점과 선으로 구성되는데, 이때 점을 노드, 선을 간선이라 합니다. 신장 트리는 모든 노드, 즉 그래프의 모든 점이 연결된 연결 그래프에서 몇 개의 간선을 제거함으로써 간선을 최소한으로 가지면서, 동시에 모든 노드가 적어도 한 간선에 연결되어 있도록 한 그래프입니다. 이때, 그래프에 사이클이 만들어져서는 안 되며, 노드가 n개일 때 (n – 1)개의 간선을 갖습니다. 신장 트리 중에서 사용된 간선의 가중치의 합이 최소인 트리를 최소 신장 트리라고 합니다. 여기서 가중치란, 간선을 지날 때 드는 거리, 시간 등 비용을 뜻합니다. 아래의 그림을 보면, 왼쪽이 연결 그래프, 오른쪽이 최소 신장 트리입니다.

최소 신장 트리를 만드는 알고리즘에는 여러 개가 있는데 그중 가장 대표적인 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘을 이해해 봅시다. 노드가 n개인 그래프에서 크루스칼 알고리즘의 작동 과정은 아래와 같습니다.
1. 간선들을 가중치에 따라 오름차순으로 정렬한다.
2. 가장 가중치가 낮은 간선을 선택해 최소 신장 트리의 집합에 포함한다.
3. 집합에 포함된 간선의 개수가 (n – 1)개가 될 때까지 정렬된 순서에 따라 간선을 선택하여 해당 간선이 사이클을 형성하지 않을 경우 최소 신장 트리의 집합에 포함한다.
글만으로는 이해가 어려울 수 있으니 예시를 통해 작동 과정을 확인해 봅시다. 아래 사진의 윗 부분은 그래프이며 아랫 부분은 그래프의 노드를 가중치를 기준으로 정렬한 것입니다.

먼저, 가장 가중치가 낮은 a – b 간선을 최소 신장 트리의 집합에 포함합니다. 그리고 다음으로 가중치가 낮은 a – d 간선을 보면, 집합에 포함된 간선과 사이클을 형성하지 않기 때문에 최소 신장 트리의 집합에 포함합니다. 다음으로 b – d 간선은 집합에 포함된 a – b, a – d 간선과 사이클을 형성하기 때문에 집합에 포함하지 않고, b – c 간선은 집합에 포함합니다. 그래프의 노드가 총 4개고, 현재 집합에 포함된 간선이 3개이므로 동작을 종료합니다. 결과적으로 네 개의 노드와 이를 잇는 간선 a – b, a – d, b – c로 이루어진 최소 신장 트리를 얻을 수 있습니다.
프림 알고리즘은 한 정점에서 시작하여 최소 신장 트리 집합을 단계적으로 확장해 나가는 방법으로, 노드가 n개인 그래프에서 프림 알고리즘의 작동 과정은 아래와 같습니다.
1. 임의로 시작 노드를 잡고 이를 최소 신장 트리 집합에 포함한다.
2. 최소 신장 트리 집합과 인접한 노드 중 가중치가 가장 작은 간선으로 연결된 노드와 이를 잇는 간선이 최소 신장 트리 집합에 포함한다.
3. 트리가 (n – 1)개의 간선을 가질 때까지 2번 과정을 반복한다.
이것 역시 예시를 통해 이해해 봅시다. 아래와 같은 그래프가 있고 시작 노드를 a로 잡았다고 가정합시다.

먼저, a 노드와 가중치가 가장 작은 간선으로 연결된 노드는 f 이므로 이를 최소 신장 트리 집합에 포함합니다. 그래프가 7개의 노드를 가지므로, 6개의 간선을 가질 때까지 이 과정을 반복합니다. 순서대로 27의 가중치를 갖는 간선과 e, 22의 가중치를 갖는 간선과 d, 12의 가중치를 갖는 간선과 c, 16의 가중치를 갖는 간선과 b, 15의 가중치를 갖는 간선과 g가 집합에 포함되어 최소 신장 트리를 얻을 수 있습니다.
이렇게 최소 신장 트리에 대해 알아봤는데요. 최소 신장 트리는 우리에게 최적의 해답을 제시하는 것으로, 도로 건설, 네트워크 구축, 이미지 프로세싱 등 다양한 분야에서 활발히 활용되고 있어 관심이 있는 친구들은 이와 관련하여 더 공부해 보는 것을 추천드려요 🙂

참고 자료
[1] 최소 신장 트리
https://ratsgo.github.io/data%20structure&algorithm/2017/11/28/MST/

 

글. 무은재학부 20학번 26기 알리미 박정은