오늘은 최소 신장 트리를 찾는 대표적인 알고리즘인 크루스칼 알고리즘, 프림 알고리즘 중 크루스칼 알고리즘에 대해 먼저 학습해보도록 하겠습니다.
최소 신장트리(MST)
신장 트리란?
v개의 정점으로 이루어진 무향 그래프에서 v-1개의 간선으로 이루어진 트리
최소 신장 트리란?
무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리
💡 노드 V개, 간선 V-1개로 이루어진 트리에서 두 정점을 이어주는 경로는 유일합니다. 왜냐하면 자식들은 유일한 부모를 가지고 있고, 루트노드가 모든 노드들을 이어주는 매개점 역할을 하기 때문입니다.
크루스칼(KRUSKAL) 알고리즘
▪️ 간선 중심으로 해결해 나가기 때문에 간선 리스트를 활용하게 됩니다.
▪️ 간선을 하나씩 선택해서 최소 신장 트리(MST)를 찾습니다.
▪️ 그리디적인 측면에서 먼저 선택된 간선들은 나보다 유리하다고 판단하고 뒤로 돌아가지 않습니다.
▪️ 크루스칼 알고리즘은 간선이 적을 경우 활용합니다.
▪️ 시간복잡도 O(ElogE + E) -> O(ElogE)
크루스칼 알고리즘의 동작 방법은 다음과 같습니다.
- 모든 간선을 가중치에 따라 오름차순 정렬 진행하기.
- 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시키기.
⚠️ 단, 싸이클이 존재할 경우 남은 간선 중 다음으로 가중치가 낮은 간선을 선택하기. - v-1개의 간선이 선택될 때까지 2번을 반복한다
그렇다면 싸이클이 발생했는지 어떻게 확인하며, 트리를 어떻게 증가시킬 수 있을까?
💡 이전에 공부했던 서로소 집합 Union-Find 알고리즘을 활용해 union 작업을 진행했을 때 만약 union을 할 수 없다면 즉, Find(x)==Find(y) 대표자가 같다면 싸이클이 발생한다고 판단할 수 있습니다.
최종적으로 만들어진 최소신장트리는 하나의 집합 즉, 서로소 집합이 1개입니다.
이러한 크루스칼 알고리즘 내용을 코드를 통해 확인해보면 다음과 같습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/*
시간 복잡도에서는 정렬이 가장 많은 부분을 차지함
O(ElogE + E) -> O(ElogE)
따라서, 간선의 개수가 많으면 정렬 시간 오래걸림
*/
public class MSTKruskalTest {
static class Edge implements Comparable<Edge>{
int from,to,weight;
public Edge(int from, int to, int weight) {
super();
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
}
static Edge[] edgeList;
static int V,E;
static int[] parents;
static void make() { // 최소 단위 서로소 집합 만들기
parents = new int[V];
for (int i = 0; i < V; i++) {
parents[i]=i;
}
}
static int find(int x) {
if(parents[x]==x) return x;
return parents[x]=find(parents[x]); // path 압축
}
static boolean union(int x, int y) {
if(find(x) == find(y)) return false; // 싸이클 발생으로 해석
parents[find(y)] = parents[find(x)];
return true;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
edgeList = new Edge[E];
for (int i = 0; i < E; i++) { // 간선리스트 만듬
st = new StringTokenizer(br.readLine()," ");
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
edgeList[i] = new Edge(from,to,weight);
}
// 간선리스트를 가중치 기준 오름차순 정렬
Arrays.sort(edgeList);
// V개의 정점으로 make-set 작업 진행
make();
int totalCost = 0; // MST 비용
int EdgeCnt = 0; // 연결된 간선수
for (Edge edge : edgeList) { // 비용이 작은 간선순서대로 꺼내어 처리 진행
if(union(edge.from,edge.to)) { // union-set 가능하면 EdgeCnt가 V-1이 될때까지 진행
totalCost+=edge.weight;
if(++EdgeCnt==V-1) break;
}
}
System.out.println(totalCost);
}
}
크루스칼 알고리즘이 어떻게 동작하는지 그리고 서로소 집합을 정확히 이해하고 있다면 코드를 짜는데 큰 어려움이 없습니다!
다음 백준 문제를 코드를 보지 않고 스스로 작성해보면서 이해도를 테스트하면 좋을 것 같습니다 😃
https://www.acmicpc.net/problem/1197
