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

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

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

동작방식

시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법

1. 시작 단계에서는 시작 정점만이 MST 에 포함합니다.
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장합니다.
   • 즉, 가장 낮은 가중치를 먼저 선택합니다.
3. 위의 과정을 트리가 N-1 개의 간선을 가질 때까지 반복합니다.

시간복잡도

기본적으로 O(N^2) 의 시간복잡도를 가지고 있습니다. 우선순위 큐를 사용한다면 O( E logV)의 시간복잡도를 가집니다.

참고사이트

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.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class B implements Comparable<B>{
	int n;
	int dist;
	
	B (int a, int b){
		this.n = a;
		this.dist = b;
	}

	@Override
	public int compareTo(B tar) {
		if(tar.dist < this.dist) return 1;
		if(tar.dist > this.dist) return -1;
		return 0;
	}
	
	
}

public class MST_프림 {

	public static void main(String[] args) throws IOException {
		
		System.setIn(new FileInputStream("input\\prim.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());
		
		int[] used = new int[N+1]; // 방문 여부 (0: 미방문, 1: 방문)
		
		ArrayList<ArrayList<B>> alist = new ArrayList<ArrayList<B>>();
		for(int i=0; i<=N; i++) {
			alist.add(new ArrayList<B>());
		}
		
		StringTokenizer st = null;
		for(int m=1; m<=M; m++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int dist = Integer.parseInt(st.nextToken());
			
			alist.get(a).add(new B(b, dist));
			alist.get(b).add(new B(a, dist));
		}
		
		PriorityQueue<B> pq = new PriorityQueue<B>();
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(1); // 임의의 한 노드를 지정
		int sumDist = 0;
		
		while(!q.isEmpty()) {
			int currentNode = q.poll();
			used[currentNode] = 1; // 방문표시
			
			// 현재 노드에 연결된 간선을 pq에 넣음(방문한 노드는 제외)
			for(int i=0; i<alist.get(currentNode).size(); i++) {
				if(used[alist.get(currentNode).get(i).n] != 1) {
					pq.add(alist.get(currentNode).get(i));
				}
			}
			
			while(!pq.isEmpty()) {
				B tar = pq.poll();
				
				if(used[tar.n] == 1) continue; // 방문한 노드면 pass
				
				used[tar.n]= 1;// 방문표시
				sumDist += tar.dist;
				q.add(tar.n); // 연결된 노드를 큐에 넣어줌
				break; // pq에서 방문하지 않은 노드로 가는 가장 dist가 작은 것을 석택해주었으니 여기서 멈춤
			}
		}
		
		bw.write("# " + sumDist);
		
		bw.close();
		br.close();
		
	}
}