[Theory] Graph 5. MST - PRIM

728x90

    PRIM 알고리즘은 하나의 정점에서 파생된 간선들 중에서 하나를 선택해서 MST를 만들어 가는 방식이다. 

알고리즘의 동작방식은 다음과 같다.

1. 시작은 아무 정점이든 상관 없다. 
2. 시작한 정점 및 인접하는 정점들 중 최소비용의 간선을 선택한다.
3. 모든 정점이 선택될 때 까지 계속 반복한다. 

[동작 과정]

보통 Prim의 경우, 간선들의 최소를 골라내기 위해 PriorityQueue를 사용하기도 하지만, 아래 코드에서는 이를 사용하지 않고, 코드로 그대로 나타내었다. 

1. 먼저 신장트리에 연결되지 않은 정점 중에서 edge비용이 최소인 정점을 골라낸다.
2. 이어서 신장트리에 포함되지 않은 정점들 중에서 최솟값이 나오면 업데이트 한다.

for(int c=0; c<N; c++) {
	int min = Integer.MAX_VALUE;
	int minVertex = 0;
    // 신장트리에 연결되지 않은 정점중 minEdge비용이 최소인 정점
    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];
		}
	}
}

 

- 전체 코드

package com.ssafy.disjointset;

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

public class MST2_Prim {

	public static void main(String[] args) throws NumberFormatException, 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;
		
		for(int c=0; c<N; c++) {
			int min = Integer.MAX_VALUE;
			int minVertex = 0;
			// 신장트리에 연결되지 않은 정점중 minEdge비용이 최소인 정점
			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);
	}

}