Kruskal Algorithm

크루스칼 알고리즘

크루스칼 알고리즘은 최소 비용 신장 부분 트리를 찾는 알고리즘입니다.

변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 O(ElogV)의 시간복잡도를 가집니다.

 

다음은 자바로서 구현한 크루스칼 알고리즘입니다.

 

import java.util.Arrays;
import java.util.Scanner;

public class Kruskal {
	static int n;
	static int c;
	static int[] root;
	static Node[] nodeList;
	static class Node{
		int from, to, weight;
		public Node(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}
	}
	public static void main(String[] args) {
		//// input
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		c = sc.nextInt(); 
		root = new int[n];
		nodeList = new Node[c];
		for(int i=0; i<c; i++) nodeList[i] = new Node(sc.nextInt(), sc.nextInt(), sc.nextInt());
		Arrays.sort(nodeList, (o1,o2) -> o1.weight - o2.weight);
		//// input end
		int ans = 0;	int cnt = 0;
		for(int i=0; i<n; i++) root[i] = i;
		for(int i=0; i<c; i++) {
			if(cnt == n-1) break;
			if(getRoot(nodeList[i].from) == getRoot(nodeList[i].to)) continue;
			union(nodeList[i].from, nodeList[i].to);
			ans += nodeList[i].weight;
			cnt++;
		}
		System.out.println(ans);
	}
	
	public static int getRoot(int n) {
		if(root[n] == n) return n;
		return getRoot(root[n]);
	}
	
	public static void union(int a, int b) {
		int rA = getRoot(a);
		int rB = getRoot(b);
		if(rA < rB) root[rB] = rA;
		else root[rA] = rB;
	}

}

5 10
0 1 5
0 2 10
0 3 8
0 4 7
1 2 5
1 3 3
1 4 6
2 3 1
2 4 3
3 4 1

output==>10

7 11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51

output==>175

 

-- 백준 관련문제 링크

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결