Typiler

신장트리(Spanning Tree)는 그래프 내의 모든 정점을 포함하는 트리입니다. MST(Minimum Spanning Tree)는 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 이야기합니다. MST는 크루스칼 그리고 프림 알고리즘이 있습니다. 여기서는 크루스칼 알고리즘을 다루겠습니다.

• 그래프 내의 간선의 숫자가 적은 희소 그래프의 경우 : 크루스칼 알고리즘
• 그래프 내의 간선의 숫자가 많은 밀집 그래프의 경우 : 프림 알고리즘

동작방식

탐욕적 방법(Greedy)을 이용하여 가중치 그래프의 모든 정점을 최소 비용으로 연결하는 방법입니다.

1. 그래프의 간선들을 가중치의 오름차순으로 정렬합니다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택합니다.
   • 즉, 가장 낮은 가중치를 먼저 선택합니다.
   • 사이클을 형성하는 간선을 제외합니다.
   • 해당 간선을 현재의 MST의 집합에 추가합니다.

시간복잡도

Union-Find 알고리즘을 이용하면 크루스칼 알고리즘의 시간 복접도는 간선들을 정렬하는 시간에 좌우됩니다.

간선 N개를 효율적으로 정렬한다면 O(N logN)의 시간복잡도를 갖는다.

참고사이트

https://hibee.tistory.com/300

기본코드

입력값

코드

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();
		
	}
	
}