[알고리즘] 크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘이란?

 

크루스칼 알고리즘은 그리디 알고리즘을 적용해 그래프의 모든 노드를 최소 비용으로

 

연결해 최소 비용 신장 트리(MST, Minimum Spanning Tree)를 구하는 알고리즘이다.

 

그리디 알고리즘

https://dheldh77.tistory.com/52

[알고리즘] Greedy Algorithm(탐욕 알고리즘)

 

신장 트리(Spanning Tree) 

 

그래프 내의 모든 정점을 포함하는 트리로 모든 정점들을 연결되어야하고, 사이클이 포함되어서는 안된다.

 

신장 트리에서 간선의 수는 n개의 정점이 주어졌을 때, n-1개가 된다. 

 

 

최소비용 신장트리(MST, Minimum Spannig Tree)

 

가능한 신장트리에서 간선의 가중치의 합이 최소가 되는 신장트리를 말한다.

 

 

크루스칼 알고리즘 과정

1. 그래프의 모든 간선들을 가중치의 오름차순으로 정렬한다.

 

2. 가중치가 가장 낮은 간선부터 선택한다.(그리디)

 

3. 간선을 연결했을 때, 사이클이 생기는지 확인한다.(Union-Find)

 

4. 사이클이 생기지 않는다면 간선을 연결하고, 2번으로 돌아간다.

 

크루스칼 알고리즘 구현

package baekjoon;

import java.util.*;
import java.io.*;

public class BOJ_1922 {
	static int[] p;
	
	public static int find(int x) {
		if(x == p[x]) return x;
		return find(p[x]);
	}
	
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		if(x > y) p[x] = y;
		else p[y] = x;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(br.readLine());
		int cost = 0;
		int n = Integer.parseInt(tk.nextToken());
		tk = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(tk.nextToken());
		
		p = new int[n + 1];
		for(int i = 0; i < n; i++) p[i] = i;
		int[][] edge = new int[m][3];
		for(int i = 0; i < m; i++) {
			tk = new StringTokenizer(br.readLine());
			for(int j = 0; j < 3; j++) {
				edge[i][j] = Integer.parseInt(tk.nextToken());
			}
		}
		
		Arrays.sort(edge, new Comparator<int[]>() {
			@Override
			public int compare(int[] cmp1, int[] cmp2) {
				if(cmp1[2] > cmp2[2]) return 1;
				else if(cmp1[2] < cmp2[2]) return -1;
				else return 0;
			}
		});
		
		for(int i = 0; i < edge.length; i++) {
			if(find(edge[i][0]) != find(edge[i][1])) {
				cost += edge[i][2];
				union(edge[i][0], edge[i][1]);
			}
		}
		
		System.out.println(cost);
		
	}
}

 

https://dheldh77.tistory.com/383

[백준] 1922번 - 네트워크 연결