프림 알고리즘
- 최소신장트리를 찾는 그리디 알고리즘
- 그래프의 모든 정점을 최소 비용으로 연결하는 트리
- 간선 중심의 크루스칼 알고리즘과 다르게, 정점 중심적 접근 방식임
- 도로망 설계나 네트워크 설계, 통신 네트워크 설계, 전력망 설계 등의 문제에 주로 활용될 수 있음
동작 원리
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);
}
}