최소 신장 트리(MST)

📌최소 신장 트리

💡 그래프에서의 최소 비용 문제

1. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 (최소 신장 트리)
2. 두 정점 사이의 최소 비용의 경로 찾기 (최단 경로)

신장 트리

• n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
• 어떤 정점도 외톨이가 되지 않도록 연결된 트리. BUT 사이클이 생기면 안된다!

최소 신장 트리 (Minimum Spanning Tree)

• 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

---

📌KRUSKAL 알고리즘

• 간선을 하나씩 선택해서 MST를 찾는 알고리즘
• 간선을 이용하기 때문에 리스트를 활용한다.

💡 알고리즘

1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴.
   ❗사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
3. N-1개의 간선이 선택 될 때까지 2를 반복.

💡 알고리즘 적용 예

💡 코드

public class Kruskal {

	static class Edge implements Comparable<Edge> {

		int start, end, weight;

		public Edge(int start, int end, int weight) {
			super();
			this.start = start;
			this.end = end;
			this.weight = weight;

		}

		@Override
		public int compareTo(Edge o) { // compareTo 나를 기준으로 o를 비교
			//return this.weight-o.weight; //간선의 부호가 모두 같을 때
			return Integer.compare(this.weight, o.weight);
		}

	}

	static int[] parents; // 부모원소를 관리(트리처럼 사용)

	private static void make() {
		parents = new int[V];
		// 모든 원소를 자신을 대표자로 만듦
		for (int i = 0; i < V; i++) {
			parents[i] = i;
		}
	}

	// a가 속한 집합의 대표자 찾기
	private static int find(int a) {
		if (a == parents[a]) return a; // 자신이 대표자.
		return parents[a] = find(parents[a]); // 자신이 속합 집합의 대표자를 자신의 부모로 : path compression
	}

	// 두 원소를 하나의 집합으로 합치기(대표자를 이용해서 합침)
	private static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if (aRoot == bRoot) return false; // 이미 같은 집합으로 합치지 않음

		parents[bRoot] = aRoot;
		return true;
	}

	static int V, E;
	static Edge[] edgeList;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());

		// 간선리스트 작성
		edgeList = new Edge[E];

		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			edgeList[i] = new Edge(start, end, weight);

		}
		Arrays.sort(edgeList); // 오름차순 정렬

		make(); // 모든 정점을 각각의 집합으로 만들고 출발

		// 간선 하나씩 시도하며 트리 만들어 감.
		int cnt = 0, result = 0;
		for (Edge edge : edgeList) {
			if (union(edge.start, edge.end)) {
				// 간선을 이어봐!!
				result += edge.weight;
				if (++cnt == V - 1) break; // 간선이 v-1개가 되면 신장 트리 완성
			}
		}

		System.out.println(result);
	}

}

---

📌PRIM 알고리즘

• 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식
• 정점 중심이기 때문에 인접행렬, 인접 리스트를 활용한다.

💡 알고리즘

1. 임의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점 선택
3. 모든 정점이 선택될 때까지 1,2 과정을 반복

• 간선이 많으면 kruskal보다 prim이 더 효율적이다.
• kruskal은 간선을 정렬해야 하기 때문에 prim보다 비효율적일 수 있다.

💡 알고리즘 적용 예

💡 코드

public class PrimTest {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		int[][] adjMatrix = new int[N][N]; //인접행렬
		boolean[] v = new boolean[N];
		int[] minEdge = new int[N];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				adjMatrix[i][j] = Integer.parseInt(st.nextToken());
			}
			minEdge[i] = Integer.MAX_VALUE;
		}

		int result = 0;
		minEdge[0] = 0; // 임의의 시작점 0의 간선비용을 0으로 세팅

		// 
		for (int i = 0; i < N; i++) {
			// 1. 신장트리에 포함되지않은 정점 중 최소간선비용의 정점 찾기
			int min = Integer.MAX_VALUE;
			int minVertex = -1; // 최소 간선비용의 정점번호

			
			for (int j = 0; j < N; j++) {
				if (!v[j] && min > minEdge[j]) {
					min = minEdge[j];
					minVertex = j;
				}
			}

			v[minVertex] = true; // 신장트리에 포함 시킴
			result += min; // 간선비용 누적

			// 2. 선택된 정점 기준으로 신장트리에 연결되지 않은 타 정점과의 간선 비용 최소로 업데이트

			for (int j = 0; j < N; j++) {
				if (!v[j] && adjMatrix[minVertex][j] != 0 && minEdge[j] > adjMatrix[minVertex][j]) 
					minEdge[j] = adjMatrix[minVertex][j];
			}

		}

		System.out.println(result);
	}

}