프림 알고리즘 (Prim Algorithm)
MST 찾기 알고리즘
매 순간 최선의 선택을 하기에 그리디 알고리즘으로 분류된다
알고리즘 과정
하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식
1. 임의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
3. 모든 정점이 선택될 때까지 2 과정을 반복
크루스칼보다는 복잡할 수 있지만,
프림을 이해하면 다익스트라 알고리즘도 쉬워진다.
서로소인 2개의 집합 (2 disjoint-sets) 정보를 유지
- 트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들
- 비트리 정점들(non-tree vertices) - 선택 되지 않은 정점들
수도 코드
// G : 그래프, r : 시작 정점, minEdge[] : 각 정점기준으로 타 정점과의 최소 간선 비용
// INF : 무한대
MST-PRIM(G, r)
result = 0, cnt = 0 // result: MST비용, cnt: 처리한 정점 수, visited[]: MST에 포함된 정점 여부
FOR u in G.V
minEdge[u] = INF
minEdge[r] = 0 // 시작 정점 r의 최소비용 0 처리
WHILE true
u = Extract-MIN() // 방문하지 않은(MST에 포함되지 않은 정점) 최소 간선 비용 정점 찾기
visited[u] = true // 방문처리
result = result + minEdge[u]; // 비용 누적
IF ++cnt == N THEN breAK; END IF // 모든 정점이 다 연결되었으면 MST 완성
FOR v in G.Adj[u] // u의 인접 정점들
// 미방문 정점 중 u->v 비용이 minEdge[v] 보다 작다면 갱신
IF visited[v] == false AND w(u,v) < minEdge[v] THEN
minEdge[v] = w(u,v)
END IF
END FOR
END WHILE
END MST-PRIM()JAVA 코드
방법 1 : 인접행렬
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int V = Integer.parseInt(br.readLine());
int[][] adjMatrix = new int[V][V]; // 인접행렬 준비
boolean[] visited = new boolean[V]; // 트리정점 여부
int[] minEdge = new int[V]; // 비트리정점 기준으로 트리정점들과 연결했을 경우 최소간선비용
StringTokenizer st = null;
for (int i=0; i<V; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j=0; j<V; j++) {
adjMatrix[i][j] = Integer.parseInt(st.nextToken());
}
}
Arrays.fill(minEdge, Integer.MAX_VALUE); // 최소값 갱신위해 max로 초기화
minEdge[0] = 0; // 임의의 시작점 0을 위해 처리
int result = 0; // 최소신장트리 비용
int c;
for (c=0; c<V; c++) {
// step 1 : 비트리 정점 중 최소간선비용의 정점 찾기
int min = Integer.MAX_VALUE;
int minVertex = -1;
for (int i=0; i<V; i++) {
if (!visited[i] && minEdge[i] < min) {
min = minEdge[i];
minVertex = i;
}
}
if (minVertex == -1) break; // 신장트리 생성이 불가능한 그래프일 때
result += min; // 간선 비용 누적
visited[minVertex] = true; // 트리 정점에 포함
// step 2 : 새롭게 트리 정점에 확장된 정점 기준으로 비트리 정점들과의 간선비용 갱신
for (int i=0; i<V; i++) {
if(!visited[i] && adjMatrix[minVertex][i] != 0 // 비트리 정점이면서 && 인접해 있을 때
&& adjMatrix[minVertex][i] < minEdge[i]) { // 더 비용이 낮으면 업데이트
minEdge[i] = adjMatrix[minVertex][i];
}
}
}
System.out.println(c == V ? result : -1);
}
}
input
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
방법2 : 인접행렬 : Heap (PriorityQueue) 를 사용해서 PRIM 을 구현해보자
비트리정점 중 트리정점 간선비용 업데이트될 때마다 PQ에 넣기
import java.io.*;
import java.util.*;
class Main {
static class Vertex implements Comparable<Vertex> {
int no, weight;
public Vertex(int no, int weight) {
super();
this.no = no;
this.weight = weight;
}
@Override
public int compareTo(Vertex o) {
return Integer.compare(this.weight, o.weight);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int V = Integer.parseInt(br.readLine());
int[][] adjMatrix = new int[V][V]; // 인접행렬 준비
boolean[] visited = new boolean[V]; // 트리정점 여부
int[] minEdge = new int[V]; // 비트리정점 기준으로 트리정점들과 연결했을 경우 최소간선비용
StringTokenizer st = null;
for (int i=0; i<V; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j=0; j<V; j++) {
adjMatrix[i][j] = Integer.parseInt(st.nextToken());
}
}
PriorityQueue<Vertex> pq = new PriorityQueue<>();
Arrays.fill(minEdge, Integer.MAX_VALUE); // 최소값 갱신위해 max로 초기화
minEdge[0] = 0; // 임의의 시작점 0을 위해 처리
pq.offer(new Vertex(0, minEdge[0]));
int result = 0; // 최소신장트리 비용
int c = 0;
while (!pq.isEmpty()) {
// step 1 : 비트리 정점 중 최소간선비용의 정점 찾기
Vertex minVertex = pq.poll();
if (visited[minVertex.no]) continue;
result += minVertex.weight; // 간선 비용 누적
visited[minVertex.no] = true; // 트리 정점에 포함
if (++c == V) break;
// step 2 : 새롭게 트리 정점에 확장된 정점 기준으로 비트리 정점들과의 간선비용 갱신
for (int i=0; i<V; i++) {
if(!visited[i] && adjMatrix[minVertex.no][i] != 0 // 비트리 정점이면서 && 인접해 있을 때
&& adjMatrix[minVertex.no][i] < minEdge[i]) { // 더 비용이 낮으면 업데이트
minEdge[i] = adjMatrix[minVertex.no][i];
pq.offer(new Vertex(i, minEdge[i]));
}
}
}
System.out.println(c == V ? result : -1);
}
} input
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
방법3 : 인접 리스트 : List<List> 로 구현
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
// 프림
// cycle check <- visit
public class Main {
static int V, E;
static long sum; // V - 1 개의 간선의 가중치의 합
static List<List<Edge>> adjList; // 인접 리스트
static boolean[] visit; // 방문(선택) 체크
static PriorityQueue<Edge> pqueue = new PriorityQueue<>((e1, e2) -> e1.c - e2.c);
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
adjList = new ArrayList<>();
for (int i = 0; i <= V; i++) { // 0 dummy
adjList.add(new ArrayList<>());
}
visit = new boolean[V + 1];
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
adjList.get(v1).add(new Edge(v2, c));
adjList.get(v2).add(new Edge(v1, c));
}
// 풀이
sum = 0;
pqueue.clear();
prim();
System.out.println(sum);
}
static void prim() {
// 시작 정점 1번 출발 (다른 번호도 상관없음)
int cnt = 1;
visit[1] = true;
pqueue.addAll(adjList.get(1)); // 1번 정점에서 갈 수 있는 모든 정점, 간선을 담는다.
while( !pqueue.isEmpty() ) {
Edge edge = pqueue.poll();
if( visit[edge.v] ) continue;
visit[edge.v]= true;
sum += edge.c; // 최소 비용 합 계산
cnt++;
if (cnt==V) break; // 모든 정점을 선택
// pqueue.addAll(adjList.get(edge.v)); // 이미 방문한 정점이 포함된다.
List<Edge> temp = adjList.get(edge.v);
int size = temp.size();
for (int i = 0; i < size; i++) {
Edge e = temp.get(i);
if (!visit[e.v]) pqueue.add(e);
}
}
}
// 특정 정점에서부터 갈 수 있는 간선
// 시작정점 X <= 다른 자료구조에 시작정점을 관리 3 -> 2, 3 -> 4
static class Edge {
int v, c;
Edge(int v, int c) {
this.v = v;
this.c = c;
}
}
}방법3 의 코드로 다음 문제를 풀어보면 정답이 나온다
input
3 3 1 2 1 2 3 2 1 3 3output
3
방법 1,2는 인접행렬을 입력으로 받고
방법3 는 간선을 입력받아 인접 리스트로 저장하는 형식으로 구현
인접행렬 : 모든 간선 정보를 저장하기에 노드가 적고, 연결이 뺵빽한 그래프에 유리
인접리스트 : 노드가 많거나, 연결이 적은 희소 그래프에 유리
뭘 쓰면 좋을지 GPT 에게 물어봤다
일반적으로 인접 리스트를 쓰라고 한다.
그래도 인접행렬 방법도 공부해놓자.
TO DO
다익스트라와 프림의 코드가 매우 유사하다
다음에는 다익스트라를 공부해보자
자두과자