그래프 이론에서 모든 정점을 연결하면서 간선의 가중치 합이 최소가 되는 트리를 말한다.
- Spanning Tree(신장 트리): 그래프의 모든 정점을 포함하고 사이클이 없는 부분 그래프
- Minimum: 가능한 모든 신장 트리 중 가중치 합이 최소인 트리
즉 네트워크 연결 비용(전선, 도로, 파이프 등)을 최소로 하면서 모든 지점을 연결하고 싶은 상황에 유용하다.
핵심 조건
- 모든 정점이 연결되어야 함 (연결 그래프)
- 사이클이 없어야 함
- 간선의 수 = (정점의 수 - 1)
- 간선 가중치의 총합이 최소여야 함
MST를 구하는 대표 알고리즘
1. 크루스칼 알고리즘 (Kruskal’s Algorithm)
크루스칼 알고리즘은 간선을 기준으로 최소 스패닝 트리를 구성하는 방법이다. 모든 간선을 가중치가 작은 순으로 정렬한 뒤 사이클이 생기지 않도록 하나씩 선택해 나간다. 사이클 여부는 Union-Find(서로소 집합) 자료구조를 사용해 효율적으로 판별한다. 이 방식은 간선의 개수가 적은 희소 그래프에서 특히 효율적이며 시간 복잡도는 간선을 정렬하는 데 걸리는 O(E log E)가 지배적이다. 구현이 간단하고 직관적이어서 코딩 테스트에서도 자주 등장한다.
예제 코드 – 백준 1197번 최소 스패닝 트리 (Kruskal)
import java.io.*;
import java.util.*;
class Edge implements Comparable<Edge> {
int from, to, weight;
Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}
public class Main {
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
edges.add(new Edge(a, b, c));
}
parent = new int[V + 1];
for (int i = 1; i <= V; i++) parent[i] = i;
Collections.sort(edges); // 가중치 기준 정렬
int sum = 0, count = 0;
for (Edge e : edges) {
// 서로 다른 집합일 때만 선택 (사이클 방지)
if (find(e.from) != find(e.to)) {
union(e.from, e.to);
sum += e.weight;
count++;
if (count == V - 1) break; // MST 완성
}
}
System.out.println(sum);
}
static int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) parent[b] = a;
}
}2. 프림 알고리즘 (Prim’s Algorithm)
프림 알고리즘은 정점을 기준으로 MST를 확장하는 방식이다. 임의의 시작 정점에서 출발하여 현재 선택된 정점 집합과 연결된 간선 중 가중치가 가장 작은 간선을 선택하고 그 간선이 연결하는 정점이 아직 방문되지 않았다면 해당 정점을 포함시킨다. 이를 반복하여 모든 정점을 방문하면 최소 스패닝 트리가 완성된다. 우선순위 큐(힙)를 사용하면 가장 작은 가중치의 간선을 효율적으로 선택할 수 있으며 간선의 개수가 많은 밀집 그래프에서 효율적이다. 시간 복잡도는 O(E log V)이다.
예제 코드 – 백준 1197번 최소 스패닝 트리 (Prim)
import java.io.*;
import java.util.*;
class Node implements Comparable<Node> {
int vertex, weight;
Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
List<List<Node>> graph = new ArrayList<>();
for (int i = 0; i <= V; i++) graph.add(new ArrayList<>());
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
graph.get(a).add(new Node(b, c));
graph.get(b).add(new Node(a, c));
}
boolean[] visited = new boolean[V + 1];
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(1, 0)); // 시작 정점
int sum = 0;
int count = 0;
while (!pq.isEmpty()) {
Node now = pq.poll();
if (visited[now.vertex]) continue;
visited[now.vertex] = true;
sum += now.weight;
count++;
if (count == V) break; // 모든 정점 포함 시 종료
for (Node next : graph.get(now.vertex)) {
if (!visited[next.vertex]) {
pq.offer(next);
}
}
}
System.out.println(sum);
}
}크루스칼 vs 프림 선택 기준 & 시간 복잡도 비교
- 크루스칼:
O(E log E)– 간선이 적은 희소 그래프에서 효율적, Union-Find로 사이클 방지 - 프림:
O(E log V)– 간선이 많은 밀집 그래프에서 효율적, 우선순위 큐로 최소 간선 선택 - 선택 기준: 간선 개수가 적으면 크루스칼, 많으면 프림이 유리하다.
📝 배운점
최소 스패닝 트리는 네트워크나 인프라 구축에서 최소 비용으로 모든 지점을 연결해야 하는 상황에서 매우 유용한 알고리즘이다. 예를 들어 전력망, 도로, 통신망 설계 문제는 MST로 모델링할 수 있다. 크루스칼과 프림은 모두 같은 결과를 내지만 그래프의 특성(희소/밀집)에 따라 성능 차이가 크다는 점이 중요하다. 크루스칼은 간선 정렬 후 Union-Find를 통해 사이클을 방지하는 것이 핵심이며 프림은 우선순위 큐로 최소 간선을 빠르게 선택하는 것이 관건이다. 실제 문제 해결에서는 데이터 크기와 구조를 분석하여 두 알고리즘 중 더 적합한 방식을 선택해야 하며 이를 통해 실행 시간과 메모리 사용을 최적화할 수 있다.
