[알고리즘] Prim 알고리즘

- 간선 수가 많을 때 kruskal 알고리즘은 불리하다.

- 간선 개수에 비해 정점의 개수가 적은 경우 정점 중심인 Prim이 유리할 수 있다. (불리한 경우도 있음)

- 간적쿠 간만프 ! (간선적으면크루스칼, 간선많으면프림)

- Prim : 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식

 

- 과정

1. 임의 정점을 하나 선택해서 시작

2. 선택한 정점과 인접한 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택

3. 모든 정점이 선택될 때까지 1, 2 를 반복

 

+ MST만들기 위해 선택된 정점과 선택되지 않은 정점들 정보를 유지

 

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().trim());
		int[][] input = new int[N][N];
		int[] minEdge = new int[N];
		boolean[] visited = new boolean[N];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				input[i][j] = Integer.parseInt(st.nextToken());
			}
			minEdge[i] = Integer.MAX_VALUE;
		}	// i 노드에서 j 노드까지의 비용을 모두 배열에 저장
		
		int minVertex, min, result = 0;
		// 0번 정점 시작으로 가정
		minEdge[0] = 0;	// 시작점 최소간선비용은 0
		
		for (int c = 0; c < N; c++) {
			// 신장트리에 포함되지 않은 정점 중 최소 간선 비용의 정점 찾기
			min = Integer.MAX_VALUE;
			minVertex = 0;	
			
			for (int i = 0; i < N; i++) {	// 이 과정은 PriorityQueue 사용하면 빠르게 수행가능(최소힙)
				if(!visited[i] && min > minEdge[i]) {	
					min = minEdge[i];	
					minVertex = i;		// 선택할 정점 저장
				}
			}
			result += min;
			visited[minVertex] = true;	// 신장트리에 포함시킴
			
			// 선택된 최소비용 정점 기준으로 신장트리에 포함되지 않은 다른 정점으로의 비용 계산하여 최소값 갱신
			for (int i = 0; i < N; i++) {
				// 아직 선택되지 않은 간선 && minVertex와 인접한 정점  && 인접한 것들 중에서 최소 가중치 간선 선택
				if(!visited[i] && input[minVertex][i] != 0 && minEdge[i] > input[minVertex][i]) {
					minEdge[i] = input[minVertex][i];
				}
			}
		}
		
	}
}

5
0 5 10 8 7 
5 0 5 3 6 
10 5 0 1 3 
8 3 1 0 1 
7 6 3 1 0

output==>10

7
0 32 31 0 0 60 51
32 0 21 0 0 0 0
31 21 0 0 46 0 25
0 0 0 0 34 18 0
0 0 46 34 0 40 51
60 0 0 18 40 0 0
51 0 25 0 51 0 0

output==>175