최소 신장 트리(Minimum Spanning Tree)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

신장 트리(Spanning Tree)란?

스패닝 트리라고도 부른다. 모든 임의의 정점이 연결된 그래프인 연결 그래프의 부분 그래프다. 모든 정점이 간선으로 연결되어 있지만 사이클이 존재하지 않는 그래프다.

연결 그래프가 주어졌을 때 생성할 수 있는 신장 트리는 유일하지 않음을 알 수 있다.

최소 신장 트리(Minimum Spanning Tree)란?

최소 비용 신장 트리(Minimum cost Spanning Tree)라고도 부르는 사람들이 있지만 대부분 최소 신장 트리로 사용한다. 그래프의 간선에 가중치 등 값이 부여될 때 이를 가중치 그래프라고 하며 그 그래프가 유향 그래프일 경우 네트워크라 부른다. 가중치가 부여된 그래프의 신장 트리를 구성하는 비용은 신장 트리를 구성하는 모든 가중치의 합이다. 즉, 최소 신장 트리는 신장 트리를 구성하는 간선들의 가중치 합이 가장 작은 신장 트리 이다. 그리고 최소 신장 트리를 구현하는 알고리즘에는 주로 2가지 알고리즘을 소개한다. 따로 자세히 정리할 크루스칼 알고리즘과 프림 알고리즘이다.

MST의 특징

• 신장 트리들 중 간선의 가중치 합이 최소이다.
• n개의 정점을 갖는 그래프에 대해 n - 1 개의 간선만을 사용해야 한다.
• 사이클이 존재해서는 안된다.
• 최소 신장 트리는 최단 경로를 보장하지 않는다.

MST 사용 문제 예시

도로, 통신 등 모든 노드를 방문해야 하는 문제들 중 구축 비용이나 소요 시간 등을 최소로 해야하는 문제들에 적용될 수 있다.

MST의 구현 알고리즘

크루스칼 알고리즘 (Kruskal's Algorithm)

그리디 알고리즘 기반으로 구현한다. MST가 최소 비용의 간선으로 구성되며 사이클을 이루지 않는다는 특성에 기인해 각 단계에서 기존 선택된 간선들과 사이클을 이루지 않는 최소 비용 간선을 선택한다. 선택 시 사이클 형성 여부를 체크하는 로직을 작성해두고 사용해야 한다.

• 그래프의 간선들을 가중치를 기준으로 오름차순 정렬한다.
• 정렬된 간선들을 순서대로 탐색하며 사이클을 형성하지 않는 간선을 선택한다.
• 선택된 간선을 MST 집합에 넣는다. 집합의 원소 개수가 $V - 1$개가 될 때까지 반복한다.

구체적인 구현 방법, 시간 복잡도는 크루스칼 알고리즘(Kruskal's Algorithm)에 정리하였다.

프림 알고리즘 (Prim's Algorithm)

그리디 알고리즘 기반으로 구현한다. 다만 크루스칼 알고리즘과 동작 방식은 유사하나 간선 선택을 중심으로 동작했던 크루스칼 알고리즘과는 달리 정점을 기준으로 탐색을 진행한다. 시작 정점에서 출발하여 신장 트리 집합을 단계적으로 확장해나간다.

• 시작 시 시작 정점만이 MST 집합에 포함된다.
• 인접한 정점들 중 최소 비용 간선으로 연결된 정점을 MST 집합에 삽입한다. (삽입 시 사이클 형성 여부 체크)
• 모든 정점이 연결되도록 $V - 1$개의 간선을 갖게될 때까지 반복한다.

구체적인 구현 방법, 시간 복잡도는 프림 알고리즘(Prim's Algorithm에 정리하였다.

관련 링크

크루스칼 알고리즘(Kruskal's Algorithm

프림 알고리즘(Prim's Algorithm