신장트리(Spanning Tree)는 그래프 내의 모든 정점을 포함하는 트리입니다. MST(Minimum Spanning Tree)는 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 이야기합니다. MST는 크루스칼 그리고 프림 알고리즘이 있습니다. 여기서는 크루스칼 알고리즘을 다루겠습니다.
- 그래프 내의 간선의 숫자가 적은 희소 그래프의 경우 : 크루스칼 알고리즘
- 그래프 내의 간선의 숫자가 많은 밀집 그래프의 경우 : 프림 알고리즘
동작방식
탐욕적 방법(Greedy)을 이용하여 가중치 그래프의 모든 정점을 최소 비용으로 연결하는 방법입니다.
- 그래프의 간선들을 가중치의 오름차순으로 정렬합니다.
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택합니다.
- 즉, 가장 낮은 가중치를 먼저 선택합니다.
- 사이클을 형성하는 간선을 제외합니다.
- 해당 간선을 현재의 MST의 집합에 추가합니다.
시간복잡도
Union-Find 알고리즘을 이용하면 크루스칼 알고리즘의 시간 복접도는 간선들을 정렬하는 시간에 좌우됩니다.
간선 N개를 효율적으로 정렬한다면 O(N logN)의 시간복잡도를 갖는다.
참고사이트
https://hibee.tistory.com/300
기본코드
입력값
7 11 1 2 2 2 7 7 7 6 9 6 5 23 5 4 1 4 1 10 1 3 3 2 3 3 3 7 4 3 6 3 3 5 6 |
코드
package study.graph;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class A implements Comparable<A>{
int a;
int b;
int dist;
A (int a, int b, int dist){
this.a = a;
this.b = b;
this.dist = dist;
}
@Override
public int compareTo(A tar) {
if(tar.dist < this.dist) return 1;
if(tar.dist > this.dist) return -1;
return 0;
}
}
public class MST_크루스칼 {
static int[] uArr = null;
public static int getFind(int tar) {
if(uArr[tar] == 0) return tar;
int ret = getFind(uArr[tar]);
uArr[tar] = ret;
return ret;
}
public static void setUnion(int t1, int t2) {
int a = getFind(t1);
int b = getFind(t2);
if(a == b) return;
uArr[b] = a;
}
public static void main(String arg[]) throws IOException{
System.setIn(new FileInputStream("input\\kruskal.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine()); // 정점의 개수
int M = Integer.parseInt(br.readLine()); // 간선의 개수
PriorityQueue<A> pq = new PriorityQueue<A>();
StringTokenizer st = null;
for(int j=0; j<M; j++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int dist = Integer.parseInt(st.nextToken());
pq.add(new A(a, b, dist)); // 큐에 모든 간선을 넣는다.
pq.add(new A(b, a, dist));
}
uArr = new int[N+1];
int sumDist = 0;
while(!pq.isEmpty()) {
A tar = pq.poll();
int start = tar.a;
int end = tar.b;
int a = getFind(start); // start 의 부모(root) 확인
int b = getFind(end); // end 의 부모(root) 확인
if(a == b) continue; // 부모가 같다면 사이클이 형성되어 있다고 판단하여 다음으로 진행
setUnion(start, end); // 두개의 부모가 같지 않기 때문에 간선으로 연결가능, 그렇다면 유니온하여 부모로 설정
sumDist += tar.dist; // 간선의 거리를 더한다.
}
bw.write("# " + sumDist + "\n");
br.close();
bw.close();
}
}