[알고리즘] Prim's 알고리즘

Prim's 알고리즘

• 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식
• 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지
  • 트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들
  • 비트리 정점들(non-tree vertices) - 선택 되지 않은 정점들
• 사이클 여부의 판단이 필요 없음

순서

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

코드

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

public class MST2_PrimTest {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		int[][] adjMatrix = new int[N][N];
		boolean[] visited = new boolean[N];
		int[] minEdge = new int[N]; // 신장트리에 연결된 정점에서 자신으로의 최소간선비용

		StringTokenizer st = null;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.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 c = 0; c < N; c++) { // 정점을 모두 N번 손을 뻗으면 되기 때문에

			// 신장트리에 연결되지 않은 정점 중 minEdge 비용이 최소인 정점
			int min = Integer.MAX_VALUE;
			int minVertex = 0;
			for (int i = 0; i < N; i++) {

				// 손을 뻗을 수 있는 엣지 중에 가장 작은 값 찾기
				if (!visited[i] && min > minEdge[i]) {
					min = minEdge[i];
					minVertex = i;
				}
			}

			// 최소 비용이 나오고 나면
			result += min;
			visited[minVertex] = true;

			// 기존에 뻗었던 간선 비용이 다른정점에서 뻗은 간선 비용이 더 작으면 update
			for (int i = 0; i < N; i++) {
				if (!visited[i] && adjMatrix[minVertex][i] != 0 && minEdge[i] > adjMatrix[minVertex][i]) {
					minEdge[i] = adjMatrix[minVertex][i];
				}
			}
			// !isvisited[i]: 신장트리에 포함되지 않은 정점을 연산하기 위해
			// adjMatrix[minVertex][i]: 간선이 있는 곳만 뻗어나가기 위해
			// minEdge[i] > adjMatrix[minVertex][i]: 최소값을 업데이트하기 위해
		}

		System.out.println(result);

	}

}