[ 개념 ] 34. Tree - 최소신장트리(MST)와 크루스칼(Kruskal) 알고리즘

> 최소 신장 트리(MST)

---

Minimum Spanning Tree

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

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

MST의 특징

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

MST의 사용사례

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

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

MST의 구현방법

1. Kruskal MST 알고리즘

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

• MST가

  1. 최소 비용의 간선으로 구성되고
  2. 사이클을 포함하지 않음의 조건에 근거하여
  • 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 하는 것이다.

• 간선 선택을 기반으로 하는 알고리즘

• 이전단계에서 만들어진 신장트리와는 상관없이 무조건 최소 간선만을 선택

• 그래프 내에 적은 숫자의 간선만을 가지는 '희소 그래프'에서 사용하기 적합하다

과정

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

주의!

• 다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클을 생성하는지를 체크해야한다.
  • 새로운 간선이 이미 다른 경로에 의해 연결되어 있는 정점들을 연결할 때 사이클이 형성된다.
  • 즉, 추가할 새로운 간선의 양끝 정점이 같은 집합에 속해 있으면 사이클이 형성된다.
• 사이클 생성 여부를 확인하는 방법은
  • 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해있는지를 먼저 검사해야한다.( union-find 알고리즘 이용! )

2. Prim MST 알고리즘

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

• 정점 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법
• 그래프 간선이 많이 존재하는 '밀집 그래프'에서 사용하기 적합하다

과정

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

MST 관련 문제

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