최소 신장 트리(MST)
V개의 정점이 존재할 때 순환이 존재하지 않고, 가중치 합이 최소가 되는 무방향 가중치 그래프를 최소 신장 트리(MST)라고 한다. MST를 만들기 위해 사용하는 알고리즘은 두 개가 존재하는데, Prim 알고리즘과 서로소 집합(Union & Find)을 이용하는 Kruskal 알고리즘이다.
구현을 위해서 다음과 같은 공통 인접 행렬을 두 알고리즘 모두 공유한다.
// 정점 수
int V = 4;
// 0은 연결되지 않았다고 간주한다.
int[][] adjMatrix = {
{0, 1, 3, 0},
{1, 0, 2, 4},
{3, 2, 0, 5},
{0, 4, 5, 0}
};
Prim 알고리즘
정점을 이용하여 MST를 구성하는 알고리즘이다. 하나의 임의 정점을 선택하여 시작했을 때, 그 과정은 다음과 같다.
- 선택한 정점과 인접하는 정점 중 최소 비용의 간선이 존재하는 정점을 선택하여 연결
- 모든 정점이 선택될 때 까지 1번 과정을 반복
바로 구현해보도록 하자.
구현
정점 정보를 저장할 객체 만들기
구현을 위해서 우선순위 큐를 사용할 것이다. 자바에서 우선순위 큐를 사용하려면 저장할 객체에 Comparable을 구현하던가, 아니면 생성자에 Comparator를 넘겨줘야한다.
따라서 객체에 Comparable을 구현하여 정점의 정보를 가진 객체를 생성하여 우선순위 큐에 삽입할 때 가중치를 기준으로 오름차순 정렬이 되도록 하였다.
class Edge implements Comparable<Edge> {
int vertex;
int weight;
public Edge(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
}
MST 만들기
시작 정점부터 MST를 만드는 것은 간단하다. 우선순위 큐에서 poll()을 하면 가장 가중치가 적은 정점 객체가 반환된다. 이때 두 개의 상황이 생기는데, 정점이 이미 트리에 속했을 경우와 다른 하나는 비트리 정점인 경우이다.
따라서 정점 수만큼의 크기를 가진 방문 배열을 두어서 큐에서 반환받은 객체가 이미 방문을 한 경우에는 다음 요소를 큐에서 다시 반환 받도록 하면 된다.
boolean[] visited = new boolean[V];
while (!pq.isEmpty()) {
Edge current = pq.poll();
// 이미 방문한 정점이면 다음 요소를 반환 받도록 continue
if (visited[current.vertex]) continue;
// 정점 포함 처리
visited[current.vertex] = true;
// MST 구성에 필요한 가중치의 합
cost += current.weight;
count++;
// 모든 정점이 트리에 포함되었는지 확인
if (count == V) break;
// 해당 정점에서 연결된 간선을 우선순위 큐에 추가
for (int i = 0; i < V; i++) {
// 방문한 정점이 아니면서 유효한 정점인 경우
if (!visited[i] && adjMatrix[current.vertex][i] > 0) {
pq.offer(new Edge(i, adjMatrix[current.vertex][i]));
}
}
}
방문한 정점이 아니면서 인접 행렬에 유효한 정점인 경우에는 해당 정점의 다음 정점과 가중치 정보를 가진 객체를 만들어서 삽입한다.
전체 코드
전체 코드는 다음과 같다.
import java.util.*;
public class Prim {
public static void main(String[] args) {
// 정점 수
int V = 4;
int[][] adjMatrix = {
{0, 1, 3, 0},
{1, 0, 2, 4},
{3, 2, 0, 5},
{0, 4, 5, 0}
};
// 프림 알고리즘 시작
boolean[] visited = new boolean[V]; // 방문 여부
PriorityQueue<Edge> pq = new PriorityQueue<>(); // 우선순위 큐
pq.offer(new Edge(0, 0)); // 시작 정점 (0번) 추가
int cost = 0; // MST 비용
int count = 0; // 트리에 포함된 정점 수
while (!pq.isEmpty()) {
Edge current = pq.poll();
// 이미 방문한 정점이면 스킵
if (visited[current.vertex]) continue;
// 정점 포함 처리
visited[current.vertex] = true;
cost += current.weight;
count++;
// 모든 정점이 트리에 포함되었는지 확인
if (count == V) break;
// 해당 정점에서 연결된 간선을 우선순위 큐에 추가
for (int i = 0; i < V; i++) {
if (!visited[i] && adjMatrix[current.vertex][i] > 0) {
pq.offer(new Edge(i, adjMatrix[current.vertex][i]));
}
}
}
// MST의 총 비용 출력
System.out.println(count == V ? cost : -1);
}
}
class Edge implements Comparable<Edge> {
int vertex;
int weight;
public Edge(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
}
정리하자면 최소 가중치를 가지는 간선을 우선으로 연결을 하되, 이미 방문한 정점에 대해서는 방문을 하지 않고 바로 다음 요소를 큐에서 반환받아서 처리한다.
이때 연결한 정점의 개수가 V개가 된다면 모든 정점을 연결한 최소 가중치 트리를 만족했다는 것이기 때문에 트리를 구성하는데 사용한 가중치의 합을 출력하고 아니라면 -1을 출력한다.
Kruskal 알고리즘
간선을 하나 씩 선택해나가며 MST를 구성하는 알고리즘이다. 간선이 N개 있다고 가정하면, MST를 만드는 과정은 다음과 같다.
- 모든 간선을 가중치 기준으로 오름차순 정렬한다.
- 가중치가 가장 낮은 간선부터 연결해나가면서 MST를 구성한다. 이때, 연결 직전에 트리의 순환을 확인해서 순환이 존재하면 연결하지 않고 다음 간선으로 넘어간다.
N - 1개의 간선이 선택될 때까지 2번 과정을 반복한다.
가중치 기준으로 오름차순 정렬을 하는 것은 우선순위 큐로 구현할 것이고, 트리의 순환 확인은 Union & Find 자료구조로 구현할 것이다.
구현
간선 정보를 저장할 객체 만들기
간선의 정보는 일반적으로 출발 정점, 도착 정점, 가중치의 정보를 가진다. 따라서 이를 관리하기 위해서 객체를 만들고 우선순위 큐에 저장하기 위해서 Comparable을 재정의하자.
class Edge implements Comparable<Edge> {
int start, end, weight;
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
}
Union & Find 구현
트리의 순환을 확인하기 위해서 Union & Find 자료구조를 구현해보자.
해당 자료구조는 여기에 포스팅 하였다.
static int[] parents;
static void make() {
parents = new int[V];
for (int i = 0; i < V; i++) {
parents[i] = i;
}
}
static int findSet(int a) {
if (parents[a] < 0) return a;
return parents[a] = findSet(parents[a]); // 경로 압축
}
static boolean union(int a, int b) {
int aRoot = findSet(a);
int bRoot = findSet(b);
if (aRoot == bRoot) return false;
// a집합에 b집합을 합병
parents[aRoot] += parents[bRoot];
parents[bRoot] = aRoot;
return true;
}
이 경우에는 간단한 확인 작업만 하면 되므로 랭크 기반 합치기는 구현하지 않아도 되지 않을까 생각하였다.
간선 정보 저장
간선 정보를 우선순위 큐에 저장해야 한다.
// 정점 및 간선 개수
V = 4;
int[][] adjMatrix = {
{0, 1, 3, 0},
{1, 0, 2, 4},
{3, 2, 0, 5},
{0, 4, 5, 0}
};
// 우선순위 큐로 간선 정렬
Queue<Edge> pq = new PriorityQueue<>(edgeList);
// 인접 행렬에서 간선 정보 추출
for (int i = 0; i < V; i++) {
for (int j = i + 1; j < V; j++) { // 중복 간선을 방지하기 위해 j = i + 1부터 시작
if (adjMatrix[i][j] > 0) {
pq.offer(new Edge(i, j, adjMatrix[i][j]));
}
}
}
MST 만들기
MST 구성을 하기 위해서는 앞서 작성했던 서로소 집합을 초기화 하여 간선을 연결할 때 마다 서로소 집합을 확인하고, 가능하면 서로소 집합을 갱신해나가면서 연결하면 된다. 이때 연결된 간선이 N - 1개면 MST가 구성되었다는 것이다.
N - 1일 때 MST임이 보장되는 이유는 간선을 중심으로 MST를 만들기 때문이다. 그리고 연결 직전에 서로소 집합을 확인하면서 순환이 생기는 것을 방지하기 때문에 이 조건을 충족하면서 연결된 간선들은 최종적으로 MST가 된다.
// 모든 정점을 대표자로 하는 단위 서로소 집합으로 생성
make();
int count = 0, cost = 0;
while (!pq.isEmpty()) {
Edge edge = pq.poll();
if (union(edge.start, edge.end)) {
cost += edge.weight;
count++;
// 최소 신장 트리 완성 조건
if (count == V - 1) break;
}
}
System.out.println(count == V - 1 ? cost : -1);
전체 코드
전체 코드는 다음과 같다.
import java.util.*;
public class Kruskal {
static int V;
static int[] parents;
public static void main(String[] args) {
// 정점 및 간선 개수
V = 4;
int[][] adjMatrix = {
{0, 1, 3, 0},
{1, 0, 2, 4},
{3, 2, 0, 5},
{0, 4, 5, 0}
};
// 우선순위 큐로 간선 정렬
PriorityQueue<Edge> pq = new PriorityQueue<>(edgeList);
// 인접 행렬에서 간선 정보 추출
for (int i = 0; i < V; i++) {
for (int j = i + 1; j < V; j++) { // 중복 간선을 방지하기 위해 j = i + 1부터 시작
if (adjMatrix[i][j] > 0) {
pq.offer(new Edge(i, j, adjMatrix[i][j]));
}
}
}
// 모든 정점을 대표자로 하는 단위 서로소 집합으로 생성
make();
int count = 0, cost = 0;
while (!pq.isEmpty()) {
Edge edge = pq.poll();
if (union(edge.start, edge.end)) {
cost += edge.weight;
count++;
// 최소 신장 트리 완성 조건
if (count == V - 1) break;
}
}
System.out.println(count == V - 1 ? cost : -1);
}
static void make() {
parents = new int[V];
for (int i = 0; i < V; i++) {
parents[i] = i;
}
}
static int findSet(int a) {
if (parents[a] < 0) return a;
return parents[a] = findSet(parents[a]); // 경로 압축
}
static boolean union(int a, int b) {
int aRoot = findSet(a);
int bRoot = findSet(b);
if (aRoot == bRoot) return false;
// a집합에 b집합을 합병
parents[aRoot] += parents[bRoot];
parents[bRoot] = aRoot;
return true;
}
}
class Edge implements Comparable<Edge> {
int start, end, weight;
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
}
두 알고리즘의 시간 비교
이것으로 MST를 구현하는 두 가지의 알고리즘을 알아봤다. 그렇다면 어떤 알고리즘이 더 뛰어난 알고리즘일까? 시간복잡도를 살펴보면 프림 알고리즘의 경우 우선순위 큐를 사용하면 O((V+E)logV)이고, 크루스칼 알고리즘은 O(ElogE+union-find 연산 횟수), (E는 간선)이다.
따라서 하나의 알고리즘만 알아도 상관 없을 수 있지만 간혹 크루스칼로 풀면 시간 초과가 발생할 수도 있기 때문에 상황에 따라서 알고리즘을 선택해야 할 것이다. 그 상황은 바로 간선의 개수를 파악하는 것이다.
정확한 정보는 아니지만 이해를 돕기 위해서 강의 시간에 정점과 간선에 개수에 따른 프림과 크루스칼의 성능을 직접 실험하셔서 올린 자료를 부분적으로 공유한다.
| 실행 횟수 | 프림 정점수 | 크루스칼 최대 간선수 | 완전 그래프 | 간선 50% | 간선 30% | 간선 20% | 간선 10% | 간선 5% |
|---|---|---|---|---|---|---|---|---|
| 200,000,000 | 10,000 | 49,995,000 | 1,278,636,148 | 614,320,574 | 357,538,966 | 232,510,271 | 111,255,635 | 53,128,068 |
| 20,000,000,000 | 100,000 | 4,999,950,000 | 161,094,721,646 | 78,047,385,823 | 45,722,994,157 | 29,897,039,454 | 14,448,524,727 | 6,974,264,863 |
이때 잘 보면 간선이 10% 이하일 때 크루스칼 알고리즘이 프림 알고리즘보다 일반적으로 빠르다는 것을 알 수 있다. 물론 이 10%라는 기준이 애매할 수도 있지만, MST 관련 문제를 풀 때 참고할만한 사항이긴 할 것이다.
댓글남기기