最小拡張ツリー(MST)

📌さいしょうのびじゅ

💡 グラフィックでの最低コストの問題

腎臓の木

最小長ツリー

📌KRUSKALアルゴリズム

💡 アルゴリズム#アルゴリズム#

💡 アルゴリズム適用例

💡 コード#コード#

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アルゴリズム

💡 アルゴリズム#アルゴリズム#

💡 アルゴリズム適用例

💡 コード#コード#

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);
	}

}