오늘은 지난번 섬 연결하기 문제에서 다뤘던 프림 알고리즘에 대해 알아보겠습니다.
프림 알고리즘이란?
프림 알고리즘은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 신장 트리(Minimum Spanning Tree)를 찾는 알고리즘입니다.
여기서 무향 그래프란 방향성이 없는 노드들이 연결되어있는 그래프 자료구조를 뜻합니다.
그래프의 자료구조 형태는 바로 아래 이미지와 같습니다.
즉, 무향 그래프는 두 노드간 방향성이 없고 연결에 대한 가중치만 있는 그래프입니다. 이 무향 그래프에서 모든 노드들을 연결하는데 있어 최소 비용의 합으로 연결되어진 최소 비용 신장 트리를 구하는 알고리즘 중 하나가 프림 알고리즘입니다.
프림 알고리즘의 개요는?
프림 알고리즘은 아래 순서를 통해 무향 그래프에서 최소 비용의 합으로 모든 노드들을 연결하는 최소 비용 신장 트리를 구할 수 있습니다.
- 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다.
- 그래프의 모든 변이 들어있는 집합을 만든다.
- 모든 꼭짓점이 트리에 포함되어 있지 않은 동안
- 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 낮은 변을 트리에 추가한다.
위 알고리즘이 종료되었을 때 만들어진 트리가 바로 최소 비용 신장 트리가 됩니다.
위에서 볼 수 있듯이 프림 알고리즘은 매 순간 최선의 조건을 선택하는 탐욕법(Greedy) 알고리즘을 바탕에 두는 점 참고하시기 바랍니다. 즉, 알고리즘의 3번에서 이미 연결된 트리와 연결되지 않은 가장 가중치가 낮은 선을 선택하는 것이 바로 순간의 최선의 조건을 선택한 것입니다.
프림 알고리즘의 동작은?
위에 표현된 무향 그래프를 예로 프림 알고리즘을 통해 최소 비용 신장 트리(MST)를 구하는 동작을 설명하겠습니다.
Step 1.
무향 그래프의 초기 그래프입니다.
Step 2.
무향 그래프에서 Start 노드를 선택합니다.
Step 3.
Start 노드와 연결된 가장 가중치가 낮은 선을 선택하여 추가된 노드를 트리에 추가합니다.
Step 4.
Step 3에서 연결된 트리와 연결된 가장 가중치가 낮은 선을 선택하여 추가된 노드를 트리에 추가합니다.
Step 5.
위에서 연결된 트리와 연결된 가장 가중치가 낮은 선을 선택하여 연결된 노드를 트리에 추가하는 동작을 반복합니다. 알고리즘이 종료되어 모든 노드가 연결된 트리, 최소 비용 신장 트리(MST)의 모습은 아래와 같습니다.
프림 알고리즘의 시간복잡도는?
시간 복잡도는 간단하게 설명드리겠습니다.
프림 알고리즘에서 활용하는 최소 우선순위 큐를 구현할 수 있는 대표적인 자료구조가 두개(Binary Heap, Array) 있습니다. 이 자료구조를 어떤 것을 선택하느냐에 따라 시간 복잡도가 달라지기에 참고하시기 바랍니다.
| 자료구조 종류 | 시간 복잡도 |
| 이진 힙(binary heap) | O(E * logV) * E: 변의 개수, V: 꼭짓점의 개수 |
| 정렬되지 않은 배열(Array) | O(V2) |
무방향 가중치 그래프에서 최소 비용 신장 트리를 구하는 프림 알고리즘을 알아보았습니다.
내용적으로 어려운 부분은 제거하고 이해하기 쉽게 설명하는데 중점을 두었으니 더 심화적인 이해가 필요하신 분들은 아래 나열된 참고한 사이트를 참고하여 추가적인 학습을 진행하시기 바랍니다.
프림 알고리즘 학습 사이트
'컴공생의 Knowledge > Algoritm Notion' 카테고리의 다른 글
| 깊이 우선 탐색(Depth First Search)을 알아보자 (feat.JS) (18) | 2022.08.01 |
|---|---|
| 너비 우선 탐색(Breadth First Search)을 알아보자 (feat.JS) (29) | 2022.07.31 |
| 자료구조 힙(Heap)은? 무엇인가? (10) | 2022.06.29 |
| 알고리즘 시간복잡도란 무엇인가? (1) | 2022.06.16 |
댓글