크루스칼 알고리즘

---

📌 간선 중심 알고리즘

---

KRUSKAL 알고리즘

• 간선을 하나씩 선택해서 MST를 찾는 알고리즘
• 간선이 적을수록 유리하다.
• 시간복잡도 : N log N (N은 간선의 개수). 정확히 표기하면 E log E + V
• 서로소 집합 (Union, Find-Set) 이해가 핵심이다.

💡 서로소 집합이란
상호 배타 집합 표현. 하나의 집합을 하나의 트리로 표현한다. 자식노드가 부모노드를 가리키며 
루트노드가 대표자가 된다.
- Make-Set(x) : x를 대표자로 만든다.
- Find-Set(x) : 원소 x의 대표자를 찾는다.
- Union(x,y) : x, y 두 집합을 합병한다. 먼저 x,y의 대표자를 찾는 작업이 필요하다. 그 후에 
			   합병이 이루어지는데, 대표자는 x,y 둘 중 하나가 된다.

과정

1. 최초 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다.
   : 사이클이 존재하면 다음으로 가중치가 낮은 간선을 선택한다. 여기서 사이클이 존재한다는 것은 '대표가 같다' 는 의미이다. 즉 특정 정점에 다른 정점이 연결되어 있음을 뜻한다.
3. N-1개의 간선이 선택될 때 까지 2번을 반복한다.
   💡 MST 특징: N개의 정점을 가지는 그래프에 대해 반드시 (N-1)개의 간선을 사용해야 한다. - MST 설명

구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;


// swea3124
public class 크루스칼 {

	static int[] boss;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		for(int t=1; t<=T; t++) {
			st = new StringTokenizer(br.readLine());
			int V = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			
			// 간선 정보 저장
			// [][0]: 시작정점, [][1]: 도착정점, [][2]: 가중치
			int[][] edges = new int[E][3];
			for(int i=0; i<E; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<3; j++) {
					edges[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			// 정렬
			Arrays.sort(edges, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return o1[2] - o2[2];
				}
			});
			
			// Make-Set. 나 자신을 대표자로 지정
			boss = new int[V+1];
			for(int i =1; i<V+1; i++) {
				boss[i] = i;
			}
			
			// MST를 만들어보자
			long ans = 0;
			int pick = 0;
			for(int i=0; i<E; i++) {
				// i번째 간선을 뽑아서 두 정점의 대표를 확인다.
				int px = findSet(edges[i][0]); 
				int py = findSet(edges[i][1]);
				
				// 각각의 대표가 다르면								
				if(px != py) {
                	// 합병
					union(px, py);
                    // 최소 가중치 중 하나로 선택 즉, 연결
					ans += edges[i][2];			
					pick++;
				}

				if(pick == V-1) break;
			}
			
			System.out.println("#"+t+" "+ans);
			
		} // tc
	} //main
	
	
	// Find-set. 대표자 찾기
	static int findSet(int x) {
		if (x != boss[x])
			boss[x] = findSet(boss[x]);
		return boss[x];
	}
	
	
	// Union. 병합
	static void union(int x, int y) {
		boss[y] = x;
	}
}

👉 '각각의 대표가 다르다' : 사이클이 아니라는 뜻이다. 혹은 아직 선택되지 않은 간선이라는 뜻이다.
👉 정렬 : 양수이면 자리 바꿈, 음수이면 자리 유지