프림

1. 프림 (Prfim) 이란?

그리디 알고리즘과 우선순위 큐를 활용해 그래프 내에서 최소 스패닝 트리를 구하는 알고리즘이다.

2. 동작 원리

가중치 최소 비용 오름차순인 우선순위 큐를 활용해 계산 당시마다 미방문 정점 중 최소 간선 비용을 가진 정점을 뽑아내서 방문처리 하고 해당 정점에서 갈 수 있는 미방문 정점을 다시 큐에 넣는 식으로 최소 스패닝 트리를 구한다.

(목적지, 현 방문 정점에서 목적지까지의 간선 비용)인 클래스를 만든다. 이것의 객체를 O라고 하겠다.

모든 O가 간선의 비용이 낮은 순으로 오름차순 되도록 우선순위 큐를 만들고 시작 정점을 넣는다.

다음의 과정을 큐가 빌 때까지 반복한다.

Queue.poll() 해서 객체 O를 하나 뽑는다.
만약 뽑은 객체 O가 이미 방문한 정점이면 넘어간다.
O에서 갈 수 있는 정점 중 미방문인 정점을 (목적지, 현 방문 정점에서 목적지까지의 간선 비용) 형태로 큐에 넣는다.

⚠️ 주의점

클래스 객체로 넣는 (목적지, 목적지까지의 간선 비용) 에서 간선 비용은 시작 정점에서의 도착 정점까지의 누적 비용이 아니다. 딱 그 간선 비용 그 자체이다. 프림은 최소 거리 구하는 알고리즘이 아닌 MST를 구하는 알고리즘으로 누적 값이 필요없다. 또한 누적된 계산을 하지 않기에 모든 간선이 단절 독립(서로 영향 x)되어 있어 음수 가중치가 있는 경우에도 MST 계산이 가능하다.

❓ 우선순위 큐에서 뺀 간선이 사이클을 만들지 않으리란 확신을 어떻게 하나요?

방문 처리 된 정점은 가지 않으니까 애초에 사이클이 생길 수가 없음.

❓우선순위 큐에서 뺀 간선이 최소 스패닝 트리에 일원이라는 것은 어떻게 확신하나요?

우선순위 큐에서 poll()해서 나온 값 중 최초 방문한 정점만 매번 포함시키고 있다.
우선순위 큐는 가중치가 낮은 것이 항상 먼저 나오므로, 동일한 정점까지의 경로 중 항상 작은 것이 먼저 나올 것이다. 따라서 최소 스패닝 트리의 일원임을 확신할 수 있다.

(0) 사전 준비

준비물

(목적지 정점 번호, 간선 가중치) 형태의 인접 리스트

가중치 오름차순 우선순위 큐

방문 배열

(1) 출발 정점 넣기

출발 정점을 우선순위 큐에 삽입해서 프림 알고리즘 실행

우선 출발정점으로 가는 가중치는 0이기 때문에 (출발 정점, 0)인 객체를 우선순위 큐에 넣는다.

출발 정점에서 갈 수 있는 모든 간선과 그 목적지를 객체화하여 우선순위 큐에 넣는다.

(2) 큐가 빌 때까지 위의 과정 반복

다음 (4,3)은 4가 이미 방문한 정점이므로 생략한다.

3. 예시 코드

최소 스패닝 트리의 가중치를 구하는 프림 코드


import java.util.*;
import java.io.*;

public class Main {
  static class Dest implements Comparable<Dest> {
  	int v;
    int w;
    public Dest(int v, int w) {
    	this.v = v;
    	this.w = w;
    }

    @Override
    public int compareTo (Dest obj) {
    	return this.w - obj.w;
    }

  }
  static int V,E;
  static ArrayList<Dest> [] lists;
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    V = Integer.parseInt(st.nextToken());
    E = Integer.parseInt(st.nextToken());
    lists = new ArrayList [V+1];

    for(int i = 1; i <= V; i++) {
    	lists[i] = new ArrayList<>();
    }

    for (int i = 0; i < E; i++) {
    	st = new StringTokenizer (br.readLine());
      	int start = Integer.parseInt(st.nextToken());
      	int end = Integer.parseInt(st.nextToken());
      	int weight = Integer.parseInt(st.nextToken());
      	lists[start].add(new Dest(end, weight));
      	lists[end].add(new Dest(start, weight));
    }
    System.out.println(prim(1));

  }

  public static int prim(int start) {
  	int weight = 0;
    boolean [] check = new boolean[V+1];
    PriorityQueue<Dest> pq = new PriorityQueue<>();
    pq.add(new Dest(start,0));

    while(!pq.isEmpty()) {
    	Dest now = pq.poll();
    	// 이미 방문한 점이면 넘어간다.
      	if(check[now.v]) continue;
      	// 미방문 지점이면 이제 최소 스패닝 트리의 일원이므로 정점 방문 체크 및 MST 비용 누적 계산 처리
      	// 새로운 후보 간선들을 체크해서 우선순위 큐에 넣는다.
      	check[now.v] = true;
      	weight += now.w;
      	for(Dest next : lists[now.v]) {
        	if(check[next.v]) continue;
          	pq.add(new Dest(next.v, next.w));
        }
    }
    return weight;
  }
}