프림 알고리즘

 

  • 최소신장트리를 찾는 그리디 알고리즘

  • 그래프의 모든 정점을 최소 비용으로 연결하는 트리

  • 간선 중심의 크루스칼 알고리즘과 다르게, 정점 중심적 접근 방식임

  • 도로망 설계나 네트워크 설계, 통신 네트워크 설계, 전력망 설계 등의 문제에 주로 활용될 수 있음

 

 

 

 

동작 원리

1. 임의의 정점에서 시작해 최소 비용인 간선을 선택(연결)

 

2. 선택한 간선의 끝에 있는 정점을 방문 체크하고, 그 정점에서 나가는 간선 중 가장 작은 간선을 선택

 

3. 같은 방법으로 모든 정점이 연결될 때까지 반복

 

 

 

 

 

장점

  • 정점 중심의 알고리즘으로, 간선이 많은 그래프에 유리함

 

단점

  • 간선의 수가 적을 경우 타 알고리즘에 비해 효율이 떨어질 수 있음

  • 가중치를 저장하고 관리하는 과정에서 추가적인 메모리가 필요할 수 있음

 

 

 

구현

1. 방문체크배열(visited), 인접배열(adjArr), 시작점으로부터의 거리(dist)를 저장할 배열이 필요

 

2. dist배열을 모두 무한대로 설정하고, 시작점만 0으로 변경

 

3. dist배열에서 최소값을 가지면서, 아직 방문하지 않은 정점을 탐색 정점으로 선택 & 방문 체크

 

4. 인접배열을 통해 탐색하고자 하는 정점에서 출발하는 모든 간선 중 가장 낮은 간선을 선택하고, dist배열에 가중치 기록

 

5. dist 배열에서 최소값을 가지면서 아직 방문하지 않은 정점이 바로 다음 정점임

 

import java.util.Arrays;
import java.util.Scanner;

public class Prim {
	
	static final int INF = Integer.MAX_VALUE;
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int V = sc.nextInt(); //정점의 번호 0번부터 시작
		int E = sc.nextInt(); //간선의 수
		
		//인접행렬 방식으로 
		int[][] adjArr = new int[V][V];
		
		for(int i = 0 ; i<E; i++) {
			int A = sc.nextInt();
			int B = sc.nextInt();
			int W =sc.nextInt();
			
			adjArr[A][B]=adjArr[B][A] = W; //무향
		} //입력 끝
		
		//방문체크 배열
		boolean[] visited = new boolean[V]; //해당 정점 선택
		int[] dist = new int[V]; // 선택한 간선의 가중치
		
		// dist 배열 무한대로 초기화
		for(int i = 0 ; i<V ; i++) {
			dist[i] = INF;
		}
		
		//시작 정점 선택
		dist[0] = 0; 
		int ans = 0;
		//가중치 배열을 돌면서 가장 값이 낮은것을 선택
		for(int i = 0 ; i<V; i++) { //V번 돌아도 괜찮아~
			int min = INF;
			int idx = -1;
			//가장 작으면서 아직 방문하지 않은 정점 선택
			for(int j = 0; j<V; j++) {
				if(!visited[j] && dist[j] < min) {
					min = dist[j];
					idx = j;
				}
			}
			visited[idx] = true; //방문체크
			ans += dist[idx];
			//방문하지 않았고 갱신할 수 있으면 갱신해 (idx)
			for(int j = 0 ; j<V; j++) {
				if(!visited[j] && adjArr[idx][j] != 0 && dist[j] > adjArr[idx][j]) {
					dist[j] = adjArr[idx][j];
				}
			}
		}
		
		System.out.println(ans);
		
		
		
		
		
		
		
		
		
	}
	
	
	
	
}