크루스칼 알고리즘 (Kruskal Algorithm)

1. 신장트리 : 그래프의 모든 정점과 간선의 부분집합으로 구성되는 트리

 

2. 최소신장트리(MST) : 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리

- 무방향 가중치 그래프

- 그래프의 가중치의 합이 최소여야 한다.

- N개의 정점을 가지는 그래프에 대해 반드시 (N-1) 개의 간선을 사용해야 한다.

- 사이클을 포함해서는 안된다.

 

3.  Kruskal Algorithm

- 탐욕적인 방법을  이용하여 가중그래프(가중치를 간선에 할당한 그래프)의 모든 정점을 최소비용으로 연결하는 최적해를 구하는 것

- 간선을 하나씩 선택해서 MST를 찾는 알고리즘

- 동작과정

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

  ② 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.

      a. 가중치가 가장 낮은 간선을 선택한다.

      b. 사이클이 형성되면 다음 간선을 선택

  ③ 해당 간선을 MST 집합에 추가한다. (정점의수-1)개의 간선이 선택될때 까지 반복

---

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

public class Kruskal {
	static int[] parents;
	static int[] rank;
	
	// 입력은 첫줄에 정점의 갯수와 간선의 갯수가 들어오고
	// 그 다음줄부터 간선의 정보가 정점1 정점2 가중치로 간선의 갯수만큼 들어옴
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		parents = new int[V];
		rank = new int[V];
		int[][] edges = new int[E][3];
		for(int i=0; i<E; i++) {
			edges[i][0] = sc.nextInt(); // 정점1
			edges[i][1] = sc.nextInt(); // 정점2
			edges[i][2] = sc.nextInt(); // 가중치
		}
		
		// 간선들의 가중치 오름차순 정렬
		Arrays.sort(edges, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				// o1[2] o2[2]
				return Integer.compare(o1[2],  o2[2]);
			}
		});
		
		// 각 정점에 대해 유니온파인드 연산 준비.
		for(int i=0; i<V; i++) makeSet(i);
		
		int result=0;
		int cnt = 0;
		for(int i=0; i<V-1; i++) {
			int a = findSet(edges[i][0]);
			int b = findSet(edges[i][1]);
			if(a==b) continue;
			union(a, b);
			// 간선을 선택.
			result += edges[i][2];
			// 정점의 갯수 -1번 반복하면 그만
			cnt++;
			if(cnt == V-1) break;
			
		}
		System.out.println(result);
		// 간선이 연결하는 두 정점이 같은 팀이 아니라면 한 팀으로 합쳐주고 간선 선택
		// 같은팀이라면 패스
	}
	
	static void makeSet(int x) {
		parents[x] = x;
	}
	
	static int findSet(int x) {
		if(x == parents[x]) return x;
		else {
			parents[x] = findSet(parents[x]);
			return findSet(parents[x]);
		}
	}
	
	static void union(int x, int y) {
		int px = findSet(x);
		int py = findSet(y);
		if( rank[px] > rank[py] ) {
			parents[py] = px;
		} else {
			parents[px] =py;
			if(rank[px] == rank[py]) {
				rank[py]++;
			}
		}
	}
}