최소 신장 트리(크루스칼)

1. 크루스칼 알고리즘

예를 들어 n개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있는 도로 건설.
1. 간선 데이터를 비용에 따라 오름차순으로 정렬
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생하는지 확인
1) 사이클이 발생하지 않으면 최소 신장 트리에 포함
2) 사이클이 발생하면 최소 신장 트리에 포함하지 않는다
3. 모든 간선에 대해 2번 반복

2. 시간 복잡도

간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가진다.

3. 코드

import java.util.*;


class Edge implements Comparable<Edge>{
	private int distance, nodeA, nodeB;
	
	public Edge(int distance, int nodeA, int nodeB) {
		this.distance = distance;
		this.nodeA = nodeA;
		this.nodeB = nodeB;
	}

	public int getDistance() {
		return this.distance;
	}

	public int getNodeA() {
		return this.nodeA;
	}

	public int getNodeB() {
		return this.nodeB;
	}

	@Override
	public int compareTo(Edge o) {
		if(this.distance < o.distance) {
			return -1;
		}
		return 1;
	}
}

public class 크루스칼 {

	static int v,e;
	static int[] parent = new int[1000001];
	static ArrayList<Edge> edges = new ArrayList<>();
	static int result = 0;
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		v = sc.nextInt();
		e = sc.nextInt();
		
		for(int i=1; i<=v; i++) {
			parent[i] = i;
		}
		
		for(int i=0; i<e; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int cost = sc.nextInt();
			edges.add(new Edge(cost, a, b));
		}
		
		Collections.sort(edges);
		
		for(int i=0; i<edges.size(); i++) {
			int cost = edges.get(i).getDistance();
			int a = edges.get(i).getNodeA();
			int b = edges.get(i).getNodeB();
			// 사이클이 발생하지 않을 때만 집합에 추가.
			if(findset(a) != findset(b)) {
				unionset(a,b);
				result += cost;
			}
		}
		System.out.println(result);
	}
	
	static void unionset(int a, int b) {
		int aRoot = findset(a);
		int bRoot = findset(b);
		if(aRoot<bRoot) parent[bRoot] = aRoot;
		else parent[aRoot] = bRoot;
	}

	static int findset(int x) {
		if(x == parent[x]) return x;
		return parent[x] = findset(parent[x]);
	}
}