[알고리즘 개념] 최소신장트리(MST)-Prim

[알고리즘 개념] 최소신장트리(MST)-Prim

개념

• 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나간다
• 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함된다
• 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택하여 트리를 확장해나간다

인접행렬 그래프의 MST를 구하기 위한 Prim 알고리즘 구현

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

public class algorithm_prim {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		int[][] adjMat = new int[N][N];
		int[] minEdge = new int[N];
		boolean[] visited = new boolean[N];
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				adjMat[i][j] = Integer.parseInt(st.nextToken());
			}
			minEdge[i] = Integer.MAX_VALUE;
		}
		
		int result = 0;
		minEdge[0] = 0;
		
		for(int c=0;c<N;c++) { // N개의 정점을 모두 연결
			// 신장트리에 연결되지 않은 정점 중 가장 유리한 비용의 정점을 선택
			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;
				}
			}
			
			// 선택된 정점을 신장트리에 포함시킴
			visited[minVertex] = true;
			result += min;
			
			// 선택된 정점 기준으로 신장트리에 포함되지 않은 다른 정점으로의 간선 비용을 따져보고 최소값 갱신
			for(int i=0;i<N;i++) {
				if(!visited[i] && adjMat[minVertex][i] != 0 && minEdge[i] > adjMat[minVertex][i]) {
					minEdge[i] = adjMat[minVertex][i];
				}
			}
		}
		System.out.println(result);
	}

}