[Algorithm] 최소 신장 트리를 구하는 Prim 알고리즘 with JAVA
들어가며
이번 글은 최소 신장 트리를 구하는 알고리즘 중 하나인 Prim에 대해 설명하는 글입니다. 글을 읽기 전에 아래의 링크에서 그래프 이론 및 그래프 탐색 글을 읽어보는 것을 추천합니다.
[Algorithm] 그래프 이론 및 그래프 탐색
들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한
jundyu.tistory.com
Prim 알고리즘을 설명하기 전에 최소 신장 트리에 대해 간략하게 설명하면서 시작하겠습니다.
최소 신장 트리 (MST : Minimum Spanning Tree)
1. 정의
우선 트리(Tree)의 사전적 정의는 사이클이 없고, 모든 정점이 연결된 무방향 그래프입니다. 그리고 하나의 그래프에서 모든 정점을 포함하고 사이클이 없는 부분 그래프를 신장 트리(Spanning Tree)라고 합니다.
마지막으로 신장 트리 중 간선의 가중치의 합이 최소가 될 때 최소 신장 트리(Minimum Spanning Tree)라고 합니다.
트리 VS 신장 트리?
트리는 그냥 개념 그 자체이고, 신장 트리는 그래프의 부분 집합입니다. 즉, 기존의 그래프에서 뽑아낸 트리를 신장 트리라고 합니다. 따라서 모든 신장 트리는 트리이지만 모든 트리는 신장 트리가 아닙니다.
아래의 그림으로 최소 신장 트리가 무엇인지 이해해보겠습니다.
2. 예시
위의 그림처럼 그래프가 주어졌습니다.
이때 아래처럼 다양한 신장 트리가 만들어질 수 있습니다.
다양하게 만들어지는 신장 트리 중 가장 적은 비용으로 만들 수 있는 마지막 신장 트리가 최소 신장 트리입니다.
3. 필요성
최소 신장 트리는 모든 지점을 최소한의 비용으로 연결해야 하는 경우에 자주 사용됩니다.
아래는 실생활에서 사용되는 예입니다.
- 도로망/전력망 설계
- 통신 네트워크 구축
- 배관/수도/가스 설비
등등 다양한 분야에서 필요합니다.
이제 최소 신장 트리를 구하는 알고리즘 중 하나인 Prim 알고리즘에 대해 알아보겠습니다.
Prim Algorithm
1. 개요
Prim 알고리즘은 1957년 미국 컴퓨터 과학자인 Rober C. Prim에 의해 최종적으로 고안된 MST를 구하는 알고리즘입니다.
2. 동작 방식
- 그래프의 임의의 노드 하나를 트리에 추가
- 트리와 연결된 노드 중에 현재까지 연결된 트리의 노드가 아니면서 가장 작은 가중치로 연결된 노드를 연결
- 모든 노드가 연결될 때까지 2번을 반복
3. 특징
1. 정점을 기준으로 MST를 구함
2. 우선순위 큐를 사용 → 가중치 오름차순
현재 연결된 간선 정보 중에 아직 연결되지 않고, 가장 가중치가 작은 간선을 연결해야합니다.
3. 시간 복잡도는 O(E log V)
일반적으로 데이터는 인접 리스트로 저장할 수 있도록 주어집니다. 희소 그래프의 경우 인접 리스트가 유리하고, 밀집 그래프의 경우 인접 행렬이 유리합니다. 만약 데이터가 인접 행렬로 주어진다면 시간 복잡도는 O(V^2)입니다.
4. 트리이므로 항상 양방향 그래프
트리는 양방향 그래프로 정의됩니다.
5. n-1번 추출하는 순간 MST 완성
신장 트리는 최소한의 간선으로 모든 정점을 연결하기 때문에 간선의 개수는 n-1개입니다. 따라서 연결된 간선의 개수가 n-1개가 되는 순간 while문을 종료해도됩니다.
예시로 이해하는 Prim 동작 과정
위의 그래프를 통해서 MST를 구하는 Prim 알고리즘을 설명하겠습니다.
MST를 구하기 전 시작할 노드를 정해야합니다. MST의 정의는 최소한의 비용으로 신장 트리를 구하는 것이기 때문에 어느 노드를 선택하는 지는 상관없습니다. 따라서 저는 1번 노드를 시작점으로 잡겠습니다.
또한, Prim 알고리즘에서 우선순위 큐를 사용하므로 PriorityQueue를 선언하고, 현재까지 연결된 트리의 가중치 합을 저장할 변수 total도 선언합니다.
마지막으로, 현재까지 연결된 노드를 확인할 boolean 타입의 1차원 배열도 필요합니다.
1. 우선순위 큐에 1번와 연결된 간선들 추가
시작 노드인 1번 노드와 연결된 간선은 2개입니다. 이때, 가중치를 기준으로 오름차순으로 정렬되므로 위의 그림과 같이 우선순위 큐에 삽입됩니다.
추가로 1번 노드를 방문 처리합니다.
다른 그래프 탐색 알고리즘과 다르게 방문 처리는 큐에서 추출할 때 이뤄집니다.
방문 처리를 큐에서 추출할 때 하는 이유?
프림 알고리즘은 데이크스트라 알고리즘처럼 우선순위 큐를 사용하므로 큐에 삽입된 간선 중에 가장 최선의 간선을 찾아야합니다. 따라서 큐에 삽입하는 시점에는 해당 노드가 최선인지 알 수 없고, 우선순위 큐에서 추출하는 시점이 MST를 만드는 최선의 선택임을 보장할 수 있습니다.
2. 우선순위 큐에서 가중치가 가장 낮은 노드 추출
우선순위 큐에서 가중치가 가장 낮은 간선을 추출했습니다. 2번 노드는 아직 한 번도 방문하지 않았기 때문에 방문 처리하고, total 변수에 3을 더합니다.
그리고 2번 노드와 인접한 간선들을 전부 우선순위 큐에 삽입합니다.
삽입 후 우선순위 큐는 아래와 같이 변합니다.
3. 우선순위 큐에서 가중치가 가장 낮은 노드 추출
우선순위 큐에서 가중치가 가장 낮은 노드를 추출했습니다. 2번 노드에서 4번 노드로 향하는 간선이므로 total에 1을 더하면서 4번 노드를 방문 처리합니다.
그리고 4번 노드에 인접한 노드를 우선순위 큐에 추가하면 아래와 같이 변합니다.
4. 우선순위 큐에서 가중치가 가장 낮은 노드 추출
우선순위 큐에서 가중치가 가장 낮은 노드를 추출했습니다. 2번 노드에서 5번 노드로 향하는 간선이므로 total에 2를 더하면서 5번 노드를 방문 처리합니다.
그리고 5번 노드에 인접한 노드를 우선순위 큐에 추가하면 아래와 같이 변합니다.
5. 우선순위 큐에서 가중치가 가장 낮은 노드 추출
우선순위 큐에서 가중치가 가장 낮은 노드를 추출했습니다. 3번 노드에서 4번 노드로 향하는 간선이므로 total에 3을 더하면서 3번 노드를 방문 처리합니다.
3번 노드와 인접한 노드는 전부 이미 방문했기 때문에 이번 단계에서 추가적인 삽입은 없습니다.
6. 우선순위 큐에서 가중치가 가장 낮은 노드 추출
우선순위 큐에서 가중치가 가장 낮은 노드를 추출했습니다. 4번 노드에서 7번 노드로 향하는 간선이므로 total에 4를 더하면서 7번 노드를 방문 처리합니다.
7번 노드와 인접한 노드 중 아직 신장 트리에 연결되지 않은 노드는 6번 노드밖에 없습니다. 삽입 후의 우선순위 큐는 아래와 같습니다.
7. 우선순위 큐에서 가중치가 가장 낮은 노드 추출
우선순위 큐에서 가중치가 가장 낮은 노드를 추출했습니다. 6번 노드에서 7번 노드로 향하는 간선이므로 total에 3를 더하면서 6번 노드를 방문 처리합니다.
이로써 최소 신장 트리가 만들어졌습니다.
Prim 알고리즘의 동작 방식이 이제 감이 오시나요? 우선순위 큐는 신장 트리를 확장하기 위한 후보들입니다. 현재까지 만들어진 신장 트리에 우선순위 큐에 들어있는 가장 작은 가중치의 노드를 차례대로 하나씩 붙입니다. 그렇게 n-1번이 지나면 최소 신장 트리가 만들어지는 것입니다.
Prim 알고리즘 실제 구현 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_Prim {
static int n, m, total = 0;
static List<List<Edge>> list = new ArrayList<>();
static boolean visit[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 노드 수, 간선 수, MST 비용 입력
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
// 방문 배열 초기화
visit = new boolean[n+1];
// 인접리스트 초기화
for(int i = 0; i <= n; i++) {
list.add(new ArrayList<>());
}
// 인접리스트 정보 저장
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine(), " ");
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
// 양방향 배열이므로 각각 저장
list.get(start).add(new Edge(end, c));
list.get(end).add(new Edge(start, c));
}
// Prim 알고리즘 시작
prim();
// 출력
System.out.println(total);
}
private static void prim() {
// 우선순위 큐 사용
Queue<Edge> q = new PriorityQueue<>();
/**
* 시작할 정점 1과 연결된 모든 간선을 추가해야 함
* */
q.addAll(list.get(1));
// 1번 노드는 바로 방문 처리
visit[1] = true;
// cnt는 현재까지 사용한 간선의 수
int cnt = 0;
while(!q.isEmpty()) {
Edge poll = q.poll();
// 현재 신장 트리에 이미 포함된 노드라면 연결하면 안되므로 패스
if(visit[poll.node]) {
continue;
}
// 연결되지 않은 노드라면 현재 추출한 노드가 최소 비용이므로 신장 트리에 추가
visit[poll.node] = true;
// 동시에 해당 가중치를 total에 추가
total += poll.w;
// 사용한 간선의 수가 n-1개가 되는 순간 MST 완성
if(++cnt == n-1) break;
// 새로 연결한 노드와 인접한 노드들도 전부 우선순위 큐에 추가
for(Edge out : list.get(poll.node)) {
if(!visit[out.node]) { // 방문하지 않은 경우에 추가함.
q.offer(out);
}
}
}
}
// 간선 정보를 저장하는 Edge 클래스
static class Edge implements Comparable<Edge> {
int node;
int w;
public Edge(int node, int w) {
this.node = node;
this.w = w;
}
// 간선의 가중치의 오름차순으로 정렬
@Override
public int compareTo(Edge o) {
return this.w - o.w;
}
}
}입력
7 9
1 2 3
1 4 5
2 4 1
2 5 2
3 4 3
4 5 6
4 7 4
5 7 5
7 6 3
출력
16
.
.
.
마치며
우선 Prim 알고리즘을 이용해서 최소 신장 트리를 구하는 문제를 아래와 같이 추천드립니다!
- 1197번 최소 스패닝 트리 : https://www.acmicpc.net/problem/1197
- 13418번 학교 탐방하기 : https://www.acmicpc.net/problem/13418
다음 글은 크루스칼 알고리즘으로 찾아뵙겠습니다. 드디어 그래프 관련 알고리즘도 끝이 보이네요 😊
궁금한 점이나 피드백 관련 사항은 댓글 환영합니다!