Prim 알고리즘 시간복잡도 - prim algolijeum siganbogjabdo

오늘은 지난번 섬 연결하기 문제에서 다뤘던 프림 알고리즘에 대해 알아보겠습니다.

프림 알고리즘이란?

프림 알고리즘은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 신장 트리(Minimum Spanning Tree)를 찾는 알고리즘입니다.

여기서 무향 그래프란 방향성이 없는 노드들이 연결되어있는 그래프 자료구조를 뜻합니다.

그래프의 자료구조 형태는 바로 아래 이미지와 같습니다.

즉, 무향 그래프는 두 노드간 방향성이 없고 연결에 대한 가중치만 있는 그래프입니다. 이 무향 그래프에서 모든 노드들을 연결하는데 있어 최소 비용의 합으로 연결되어진 최소 비용 신장 트리를 구하는 알고리즘 중 하나가 프림 알고리즘입니다.

프림 알고리즘의 개요는?

프림 알고리즘은 아래 순서를 통해 무향 그래프에서 최소 비용의 합으로 모든 노드들을 연결하는 최소 비용 신장 트리를 구할 수 있습니다.

1. 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다.
2. 그래프의 모든 변이 들어있는 집합을 만든다.
3. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안
   1. 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 낮은 변을 트리에 추가한다.

위 알고리즘이 종료되었을 때 만들어진 트리가 바로 최소 비용 신장 트리가 됩니다.

위에서 볼 수 있듯이 프림 알고리즘은 매 순간 최선의 조건을 선택하는 탐욕법(Greedy) 알고리즘을 바탕에 두는 점 참고하시기 바랍니다. 즉, 알고리즘의 3번에서 이미 연결된 트리와 연결되지 않은 가장 가중치가 낮은 선을 선택하는 것이 바로 순간의 최선의 조건을 선택한 것입니다.

프림 알고리즘의 동작은?

위에 표현된 무향 그래프를 예로 프림 알고리즘을 통해 최소 비용 신장 트리(MST)를 구하는 동작을 설명하겠습니다.

Step 1.

무향 그래프의 초기 그래프입니다.

Step 2.

무향 그래프에서 Start 노드를 선택합니다.

Step 3.

Start 노드와 연결된 가장 가중치가 낮은 선을 선택하여 추가된 노드를 트리에 추가합니다.

Step 4.

Step 3에서 연결된 트리와 연결된 가장 가중치가 낮은 선을 선택하여 추가된 노드를 트리에 추가합니다.

Step 5.

위에서 연결된 트리와 연결된 가장 가중치가 낮은 선을 선택하여 연결된 노드를 트리에 추가하는 동작을 반복합니다. 알고리즘이 종료되어 모든 노드가 연결된 트리, 최소 비용 신장 트리(MST)의 모습은 아래와 같습니다.

프림 알고리즘의 시간복잡도는?

시간 복잡도는 간단하게 설명드리겠습니다.

프림 알고리즘에서 활용하는 최소 우선순위 큐를 구현할 수 있는 대표적인 자료구조가 두개(Binary Heap, Array) 있습니다. 이 자료구조를 어떤 것을 선택하느냐에 따라 시간 복잡도가 달라지기에 참고하시기 바랍니다.

무방향 가중치 그래프에서 최소 비용 신장 트리를 구하는 프림 알고리즘을 알아보았습니다.

내용적으로 어려운 부분은 제거하고 이해하기 쉽게 설명하는데 중점을 두었으니 더 심화적인 이해가 필요하신 분들은 아래 나열된 참고한 사이트를 참고하여 추가적인 학습을 진행하시기 바랍니다.

프림 알고리즘 학습 사이트

• 프림 알고리즘 위키 백과
• JavaScript 기반 Prim's Algorithm

개요

◎ 프림 알고리즘이란?

◎ 그림 예시

◎ 구현 코드 - 인접 행렬 (Java)

◎ 시간 복잡도 - 인접 행렬

◎ 구현 코드 - 힙 (Java)

◎ 시간 복잡도 - 힙

◎ 특징

안녕하세요. 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) 알고리즘 기법입니다. (각 상황별 가장 좋아 보이는 선택지를 고릅니다.)

정리

● 프림 알고리즘은 가중치가 가장 작은 다른 정점을 선택하여 순회하는 MST 기법

● 그리디 알고리즘이며 길(간선)의 개수가 많을 때 사용

● 구현 방법은 인접 행렬과 힙이 존재

● 인접 행렬의 시간 복잡도는 O(N^2), 힙의 시간 복잡도는 O(ElogN)

● 코드를 이해하기에는 인접 행렬이 더 효과적이라고 생각하는 편

이상으로 프림 알고리즘에 대해 간단하게 알아보는 시간이었습니다.

읽어주셔서 감사합니다.