개요
안녕하세요. J4J입니다.
이번 포스팅은 프림 알고리즘에 대해 적어보는 시간을 가져보려고 합니다.
프림 알고리즘이란?
프림 알고리즘은 대표적인 MST 구현 알고리즘 중 하나로 정점을 기준으로 갈 수 있는 가중치가 가장 작은 길(간선)을 선택한 뒤 다음 정점을 방문하며 MST를 만드는 기법입니다.
예를 들어 A, B, C, D, E 정점이 있다고 가정해보겠습니다.
A ↔ C 가중치: 3
A ↔ D 가중치: 5
B ↔ C 가중치: 4
B ↔ D 가중치: 4
C ↔ E 가중치: 2
D ↔ E 가중치: 1
이고 A 정점에서 출발한다면 다음과 같은 순서로 정점을 방문합니다.
1-1. A에서 갈 수 있는 정점을 확인합니다. (C: 3, D: 5)
1-2. 가장 작은 가중치를 가지는 C정점을 방문합니다. (방문 A, C)
2-1. C에서 갈 수 있는 정점을 확인합니다. (A: 3, B: 4, E: 2)
2-2. 이전에 방문했던 정점들의 가중치와 비교하여 방문하지 않은 정점들의 최솟값을 확인합니다. (B: 4, D: 5, E: 2)
2-3. 가장 작은 가중치를 가지는 E정점을 방문합니다. (방문 A, C, E)
3-1. E에서 갈 수 있는 정점을 확인합니다. (C: 2, D: 1)
3-2. 이전에 방문했던 정점들의 가중치와 비교하여 방문하지 않은 정점들의 최솟값을 확인합니다. (B: 4, D: 1)
3-3. 가장 작은 가중치를 가지는 D정점을 방문합니다. (방문 A, C, E, D)
4-1. D에서 갈 수 있는 정점을 확인합니다. (A: 5, B: 4, E: 1)
4-2. 이전에 방문했던 정점들의 가중치와 비교하여 방문하지 않은 정점들의 최솟값을 확인합니다. (B: 4)
4-3. 가장 작은 가중치를 가지는 B정점을 방문합니다. (방문 A, C, E, D, B)
5-1. 더 이상 방문할 수 있는 정점이 존재하지 않아 실행이 종료됩니다.
그림 예시
위의 순서와 동일한 상황을 그림으로 표현해보겠습니다. (A: 0, B: 1, C: 2, D: 3, E: 4)
구현 코드 - 인접 행렬 (Java)
package mst;
import java.util.Arrays;
public class PrimArray {
public static void main(String[] args) {
int N = 5; // 정점의 갯수
int graph[][] = new int[N][N]; // 정점 간 가중치 저장
boolean visited[] = new boolean[N]; // 정점 방문여부
int minWeight[] = new int[N]; // 정점에 도착할 수 있는 가장 작은 가중치
init(graph, minWeight); // 초기화, graph의 모든 간선과 정점별 가중치를 모두 정수 최대값으로 초기화
// 정수 최대값인 경우는 길이 없다는 것을 의미
// 가중치 추가
add(0, 2, 3, graph);
add(0, 3, 5, graph);
add(1, 2, 4, graph);
add(1, 3, 4, graph);
add(2, 4, 2, graph);
add(3, 4, 1, graph);
int index = 0; // 시작 정점
minWeight[index] = 0;
while(index != -1) { // 다음 정점을 선택하지 못할 떄 까지 순환
visited[index] = true; // 방문 체크
for(int i=0; i<N; i++) {
if(!visited[i] && graph[index][i] != Integer.MAX_VALUE) { // 방문한 적이 없고 현재 정점에서 길(간선)이 존재할 경우
minWeight[i] = Math.min(minWeight[i], graph[index][i]);
}
}
System.out.println("선택된 정점: " + index);
System.out.println("현재 정점 별 최솟값: " + Arrays.toString(minWeight));
// 선택된 정점: 0
// 현재 정점 별 최솟값: [0, 2147483647, 3, 5, 2147483647]
// 선택된 정점: 2
// 현재 정점 별 최솟값: [0, 4, 3, 5, 2]
// 선택된 정점: 4
// 현재 정점 별 최솟값: [0, 4, 3, 1, 2]
// 선택된 정점: 3
// 현재 정점 별 최솟값: [0, 4, 3, 1, 2]
// 선택된 정점: 1
// 현재 정점 별 최솟값: [0, 4, 3, 1, 2]
index = -1; // 아래 for문을 지나도 index가 -1일 경우 갈 수 있는 다음 정점이 없음
for(int i=0; i<N; i++) {
if(!visited[i] && minWeight[i] != Integer.MAX_VALUE) { // 방문한 적이 없고 정점으로 갈 수 있는 최소 가중치 값이 존재할 경우
if(index == -1) { // 초기 저장
index = i;
} else { // 다음 정점이 이미 저장되어 있는 경우
if(minWeight[index] > minWeight[i]) { // index로 선택된 정점과 비교했을 때 더 작은 가중치를 가질 경우
index = i;
}
}
}
}
}
int sumWeight = 0; // 가중치의 합 초기화
for(int i=0; i<N; i++) { // 정점으로 갈 수 있는 최소 가중치 합들을 모두 더하기
sumWeight = sumWeight + minWeight[i];
}
System.out.println("MST를 만드는 최소 가중치 값: " + sumWeight); // MST를 만드는 최소 가중치 값: 10
}
public static void add(int v, int u, int weight, int graph[][]) { // 가중치 추가
graph[u][v] = graph[v][u] = weight;
}
public static void init(int graph[][], int minWeight[]) { // 값 초기화
int N = graph.length;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
graph[i][j] = Integer.MAX_VALUE;
}
}
for(int i=0; i<N; i++) {
minWeight[i] = Integer.MAX_VALUE;
}
}
}
시간 복잡도 - 인접 행렬
인접 행렬로 구현된 프림 알고리즘의 시간 복잡도는 O(N^2)입니다.
while문 내부를 N만큼 순회를 하고 while문 내부에 있는 for문을 N만큼 순회하므로 N x N = N^2이라는 결과가 나옵니다.
구현 코드 - 힙 (Java)
package mst;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class PrimHeap {
public static void main(String[] args) {
int N = 5; // 정점의 갯수
List<Node> graph[] = new List[N]; // 연결되어 있는 정점과 가중치 저장
for(int i=0; i<N; i++) {
graph[i] = new ArrayList<Node>();
}
int minWeight[] = new int[N]; // 정점에 도착할 수 있는 가장 작은 가중치
init(minWeight); // 초기화, 정점별 가중치를 모두 정수 최대값으로 초기화
// 정수 최대값인 경우는 길이 없다는 것을 의미
// 가중치 추가
add(0, 2, 3, graph);
add(0, 3, 5, graph);
add(1, 2, 4, graph);
add(1, 3, 4, graph);
add(2, 4, 2, graph);
add(3, 4, 1, graph);
// 힙으로 구현된 우선순위 큐
PriorityQueue<Node> pqueue = new PriorityQueue<Node>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) { // 가중치가 작은 순서대로 정렬
return o1.weight - o2.weight;
}
});
pqueue.add(new Node(0, 0)); // 0번 정점을 방문하기 위해 필요한 가중치는 0
while(!pqueue.isEmpty()) {
Node node = pqueue.poll(); // 첫 번째에 있는 노드 가져오기
if(minWeight[node.vertex] == Integer.MAX_VALUE) { // 방문하지 않은 정점일 경우
minWeight[node.vertex] = node.weight; // 최소 가중치 저장
for(int i=0; i<graph[node.vertex].size(); i++) { // 현재 정점에 연결된 다른 정점들 탐색
Node nextNode = graph[node.vertex].get(i);
if(minWeight[nextNode.vertex] == Integer.MAX_VALUE) { // 방문한 적이 없을 경우
pqueue.add(nextNode);
}
}
}
}
int sumWeight = 0; // 가중치의 합 초기화
for(int i=0; i<N; i++) { // 정점으로 갈 수 있는 최소 가중치 합들을 모두 더하기
sumWeight = sumWeight + minWeight[i];
}
System.out.println("MST를 만드는 최소 가중치 값: " + sumWeight); // MST를 만드는 최소 가중치 값: 10
}
public static void add(int v, int u, int weight, List<Node> graph[]) { // 가중치 추가
graph[u].add(new Node(v, weight));
graph[v].add(new Node(u, weight));
}
public static void init(int minWeight[]) { // 값 초기화
int N = minWeight.length;
for(int i=0; i<N; i++) {
minWeight[i] = Integer.MAX_VALUE;
}
}
private static class Node { // vertex를 방문하기 위해 필요한 가중치는 weight
int vertex;
int weight;
public Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
}
}
시간 복잡도 - 힙
힙으로 구현된 프림 알고리즘의 시간 복잡도는 O(ElogN)입니다.
여기서 E는 길(간선)의 개수의 총합을 의미합니다.
while문 내부를 N만큼 순회하고 while문 내부에 있는 for문을 각 정점마다 연결되어 있는 길(간선)의 개수만큼 순회하기 때문에 N x 정점마다 연결되어 있는 길(간선)의 개수 = 길(간선)의 개수의 총합인 E가 됩니다.
그리고 for문 내부에 있는 우선순위 큐에 저장할 때 logN만큼의 시간이 사용됩니다. (우선순위 큐는 힙으로 구현되어 있고 힙에서 삽입을 위한 시간 복잡도는 logN입니다.)
결과적으로 E만큼 순회할 때 logN만큼의 시간이 더 존재하기 때문에 E x logN = ElogN라는 값이 나옵니다. (개인적으로 실제 값은 ElogN보다는 조금 더 큰 값이라고 생각합니다.)
특징
1. 프림 알고리즘은 정점을 기준으로 구현되기 때문에 길(간선)의 개수가 많은 편일 때 주로 사용합니다.
2. 그리디(Greedy) 알고리즘 기법입니다. (각 상황별 가장 좋아 보이는 선택지를 고릅니다.)
정리
이상으로 프림 알고리즘에 대해 간단하게 알아보는 시간이었습니다.
읽어주셔서 감사합니다.
'Algorithm > Algorithm' 카테고리의 다른 글
| [Algorithm] 최단 경로 탐색(Shortest Path) - 다익스트라 알고리즘(Dijkstra Algorithm) (0) | 2021.01.31 |
|---|---|
| [Algorithm] MST - 크루스칼 알고리즘(Kruskal Algorithm) (0) | 2021.01.30 |
| [Algorithm] 최소 신장 트리(MST, Minimum Spanning Tree) (0) | 2021.01.24 |
| [Algorithm] 너비 우선 탐색(BFS, Breadth First Search) (0) | 2021.01.21 |
| [Algorithm] 깊이 우선 탐색(DFS, Depth First Search) (0) | 2021.01.18 |
댓글