[최소신장트리] PRIM

PRIM 알고리즘 또한 크루스칼과 비슷하게 최소신장트리 알고리즘 중 하나이다. 

프림 알고리즘은 하나의 정점을 시작점으로 하여 cycle을 생성하지 않는 범위 내에서, 최소 가중치를 가지는 정점을 하나씩 포함하여 N-1개의 간선까지 확대하는 알고리즘이다. 

 

1) 임의의 정점을 시작 정점으로 택해서 최소 신장트리의 루트 노드로 삽입하기.

2) 최소 신장트리에 삽입되어 있는 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사하여 이 가중치가 가장 작은 간선을 골라 최소 신장트리에 삽입

3) 모든 점이 다 연결될 때 까지 반복.

 

public class MST_PRIM {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.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(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;
		
		for(int c=0; c<N; c++) {
			//아직 연결되지 않은 정점중에 edge비용이 최소인 정점 찾아야함.
			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;
			
			for(int i=0; i<N; i++) {
				if(!visited[i] && adjMatrix[minVertex][i] != 0 && minEdge[i] > adjMatrix[minVertex][i]) {
					minEdge[i] = adjMatrix[minVertex][i];
				}
			}
		}
		System.out.println(result);
	}
}

 

개인적으로 Kruskal에 비해 이해하기가 조금 어려웠던 알고리즘이었다. 

개념 자체는 임의의 한 점부터 방문하지 않은 점 중에 가장 짧은 간선을 찾아가면 되는 건데, 뭔가 처음 봤을 때 생소해서 그런지 쉽게 다가오지 않았다. 

조금 더 익숙해지려면 더 많은 문제들을 접하면서 써 봐야 할 것 같다.