[Java] MST(최소비용신장트리) | 크루스칼 | 프림

1. Minimum Spanning Tree 

• Minimum : 가중치의 합이 최소 비용
• Spanning : 모든 vertex를 포함
• Tree : 사이클이 존재하지 않음

- 트리에 있는 모든 edge들의 weight 합이 작은 트리를 찾고자 한다.

- Spanning Tree가 여러 개 존재할 수 있듯, MST도 unique하지 않을 수 있다.

- 단, 다른 모양의 MST 있을 수 있지만 결과적으로 가중치의 합은 같아야 한다!

- MST 구성하는 알고리즘엔 (1)크루스칼 (2)프림 이 존재한다.

 

 

2. Kruskal 알고리즘 

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

1. 모든 간선을 가중치 기준 오름차순 정렬
2. 가중치 가장 낮은 간선부터 선택
   1. 단, 사이클 형성여부 확인해 (findSet) 대표가 다를 경우 (disjointSet)만 union. 
   2. 즉, 사이클 존재하면 다음으로 가중치 낮은 간선 선택
3. (V-1)개 간선 선택할 때까지 2를 반복

public class Main {
	static int[] p; // 대표를 저장할 배열
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt(); // V : 정점의 개수 정점은 0번부터 시작한다
		int E = sc.nextInt(); // E : 간선의 개수

		// 간선 배열로 그래프를 구현
		int[][] edges = new int[E][3];
		for (int i = 0; i < E; i++) {
			edges[i][0] = sc.nextInt(); // 시작 정점
			edges[i][1] = sc.nextInt(); // 도착 정점
			edges[i][2] = sc.nextInt(); // 가중치
		}

		// 1. 크루스칼 만들기 위해 가중치 기준 오름차순 정렬
		Arrays.sort(edges, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2] - o2[2]; // [2]값이 가중치임
			}
		});

		p = new int[V]; // 각 정점의 대표를 저장하는 배열
		// makeSet. 나 자신을 대표로 한다
		for (int i = 0; i < V; i++) {
			makeSet(i);
		}

		// 2. MST 만들기 위해 가중치 낮은 간선부터 (V-1)개까지 선택
		int minCost = 0; // 최소비용, 즉 가중치들의 합
		int pick = 0; // 선택된 간선의 개수

		for (int i = 0; i < E; i++) {
			// 선택한 간선이 사이클을 형성하는지 확인해야 한다
			// i번째 간선을 뽑아서 두 정점의 대표를 check
			// 대표가 같다면 pass
			// 대표가 다르면 둘은 disjoint한 집합이므로 union -> minCost 추가, pick++

			int px = findSet(edges[i][0]);
			int py = findSet(edges[i][1]);

			if (px != py) {
				union(px, py);
				minCost += edges[i][2];
				pick++;
			}

			if (pick == V - 1)
				break;

		}
		System.out.println(minCost);
	} // end of main

	private static void union(int x, int y) {
//		p[findSet(y)] = findSet(x);
		p[y] = x; // 이번 문제는 어차피 x, y를 대표값을 넣어주므로 해도됨.
	}

	// 원소 x의 대표를 가져온다
	private static int findSet(int x) {
//		if (x == p[x]) {
//			return x;
//		} else {
//			return findSet(p[x]);
//		}

		// Path compression이 적용됨
		if (x != p[x]) {
			p[x] = findSet(p[x]);
		}
		return p[x];
	}
}

 

3. Prim 알고리즘 

임의의 '정점'에서 MST 만들어 가는 알고리즘

1. 임의의 정점 하나 선택
   1. 정점 아무거나 선택해도 되는 이유? 결과적으로 모든 정점을 선택하기 때문
2. 선택 정점과 인접한 정점들 중 최소비용 간선인 정점을 선택
3. 모든 V개의 정점 선택할 때까지 1과 2를 반복

 

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt(); // V : 정점의 개수 정점은 0번부터 시작한다
		int E = sc.nextInt(); // E : 간선의 개수

		// 간선의 정보를 저장한다
		// 인접행렬을 사용한다
		int[][] adjArr = new int[V][V];
		for (int i = 0; i < E; i++) {
			int st = sc.nextInt(); // 시작 정점
			int ed = sc.nextInt(); // 도착 정점
			int w = sc.nextInt(); // 가중치
			adjArr[st][ed] = w;
			adjArr[ed][st] = w;
		}

		boolean[] visited = new boolean[V]; // 정점을 방문했는지
		int[] p = new int[V]; // 정점이 어디서 왔는지 즉, 부모를 저장
		int[] keys = new int[V]; // 정점에 연결된 간선 중 최소 가중치

		// keys 들을 무한대의 값으로 갱신해준다
		Arrays.fill(keys, Integer.MAX_VALUE);

		// 임의 정점을 선택해서 돌린다. 0번부터 시작한다
		p[0] = -1; // 0번이 시작점이다, 이미 0은 인덱스로 사용하기 때문에 다른 정점의 부모일 수도 있다. 따라서 -1로 초기화한다
		keys[0] = 0; // 모든 정점의 key들은 무한대이므로 시작정점의 key는 0으로 초기화 해둠

		int minCost = 0; // 최소값, 인덱스, MST 최소비용의 합

		// 프림 만들기
		// for는 V개수만큼 돌던 (V-1)개까지 돌던 차이 없음
		for (int i = 0; i < V - 1; i++) {
			int min = Integer.MAX_VALUE;
			int idx = -1;

			// 아직 안 뽑힌 정점들 중 가장 작은 값을 뽑는다
			for (int j = 0; j < V; j++) {
				if (!visited[j] && keys[j] < min) {
					min = keys[j];
					idx = j;
				}
			} // 이 for문이 끝나면 idx엔 이번에 선택한 정점이 들어있다
			visited[idx] = true; // idx번째 정점을 선택했다

			// 선택한 정점과 연결된 간선들을 갱신할 수 있으면 갱신하자
			for (int j = 0; j < V; j++) {
				// 방문하지 않았고 && 간선이 있으면 갱신
				// 단, 방문한 친구는 이미 최소값이기에 갱신이 일어나지 않는다 (사실 방문은 체크 안해도 됨)
				if (!visited[j] && adjArr[idx][j] != 0 && keys[j] > adjArr[idx][j]) {
					keys[j] = adjArr[idx][j];
					p[j] = idx;
				}
			}
		} // 프림 만들기

		for (int i = 0; i < V; i++) {
			minCost += keys[i];
		}
		System.out.println(minCost);
	}
}