이 글에서는 프림 알고리즘에 대해서 알아보고 어떤 경우에 사용할 수 있는 알고리즘인지, 어떻게 구현하는지 까지 알아보도록
하자.
1. 프림 알고리즘 ??
- 그래프 알고리즘은 Vertex라고 불리는 정점(Node)와 Edge라고 불리는 간선들의 조합으로 이루어져 있다.
이 때, 방향이 없는 그래프에서 모든 노드를 포함하면서, 순환되는 경로를 제거한 형태를 '스패닝 트리(Spanning Tree)' 라고
한다. 이 스패닝 트리 중에서도 그 가중치의 합이 가장 작은 스패닝 트리를 '최소 스패닝 트리(Minimal Spanning Tree : MST)'
라고 한다.
이렇게, '최소 스패닝 트리'를 만들어야 할 때, 주로 사용하는 알고리즘으로 대표적인게 '크루스칼 알고리즘'과 ,
'프림 알고리즘'이 있다. 이번 글에서는 이 '프림 알고리즘' 에 대해서 다뤄보고자 한다.
( 크루스칼 알고리즘에 대한 설명은 아래의 링크에 있습니다.
[ 크루스칼 알고리즘 알아보기(Click) ] )
2. 프림 알고리즘 동작 원리
- 프림 알고리즘의 동작 원리를 단계별로 알아보자.
1. 임의의 시작점 하나를 선택한다.
2. 이 시작점과 연결된 정점들의 거리를 업데이트 한다.
3. 선택된 정점들과 연결되어 있는 간선들 중에서, 가장 짧은 길이의 간선을 선택해서 연결해준다.
4. 가장 짧은 간선으로 연결되어 있는 정점을 선택하고, 정점들의 거리를 업데이트 한다.
5. 3 ~ 4 번의 과정은 N(전체 노드의 갯수) - 1번 만큼 반복해준다.
이렇게 말로만 봐서는 이해가 잘 안되니 그림과 함께 보도록 하자.
위의 그래프를 예시로 천천히 이해해보자.
먼저, 프림 알고리즘은 크루스칼 알고리즘과 달리, "그래프의 틀을 유지해 나가면서 MST를 형성" 하게 된다.
크루스칼 알고리즘에 대해서 간략하게만 말하자면, 크루스칼 알고리즘은 정점보다는, 간선들 중에서 가장 짧은
간선들만 선택해 나가면서 MST를 선택하게 된다. 즉, 그 만드는 과정에서 간선들이 이루는 형태를 보게 되면
전혀 그래프스럽지가 않다. 하지만, 프림 알고리즘은 하나의 정점에서부터 그래프의 틀을 유지해 나가면서 진행을
한다.
위의 그래프로 프림 알고리즘을 이해하기 전에 지금부터 "거리를 비교한다", "거리를 업데이트한다" 와 같이 '거리'라는
표현을 계속해서 사용할건데, 이 거리는 1차원 배열에 저장되어 있다고 생각하자.
즉, 현재 초기상태에는 Dist[1], Dist[2], Dist[3], Dist[4], Dist[5], Dist[6] 은 모두 무한대(INF)로 저장되어 있는
상태이다.
1. 임의의 시작점 하나를 선택한다.
- 가장 시작점을 정하는 과정이다. 가장 무난하게 '1'번 정점을 선택해보자.
2. 이 시작점과 연결된 정점들의 거리를 업데이트 한다.
- 1번을 선택하게 되는 순간, Dist[1]의 값은 0이 된다. 왜냐하면, 자기 자신으로 가는데 걸리는 거리는 0이기 때문이다.
또한, 2번, 3번 정점의 Dist 값이 각각 Dist[2] = 5, Dist[3] = 3 으로 갱신될 것이다.
왜냐하면, 2번 3번 정점은 1번과 직접적으로 연결되어 있기 때문이다.
그럼 ! 지금까지의 상태를 그림으로 한번 확인해보자.
위의 그림에서 몇 가지를 추가해서 나타내 보았다.
먼저 가장 눈에 띄는 것은, '1번 정점' 이 초록색으로 바뀌었다는 점이다. 지금부터 저렇게 초록색으로 표시된 정점은
"이미 선택된 정점이니, 더 이상 선택할 필요가 없는 정점입니다 !" 라고 이해하자.
즉 ! 우리는 모든 정점이 초록색이 될 때까지 계속해서 진행해 나갈 것이다.
그리고, 각 정점들 밑에 Dist의 값을 적어보았다. 초기에는 모두 INF 였지만, 1번과 2번과정을 통해서 Dist의 값이
저렇게 설정되었다는 것 정도는 이해했을 거라 생각한다.
3. 선택된 정점들과 연결되어 있는 간선들 중에서, 가장 짧은 길이의 간선을 선택해서 연결해준다.
- 말 그대로 한번 이해해보자. "선택된 정점들과 연결되어 있는 간선들" 은 무슨 간선들이 있을까 ??
지금, 선택된 정점은 '1'번정점 1개 뿐이고, 이 1번 정점과 연결되어 있는 간선들은, 1번과 3번을 잇는 거리가 '3'인 간선과
1번과 2번을 잇는 거리가 '5'인 간선, 총 2개가 있다.
이 중에서, 가장 짧은 길이의 간선을 선택해서 연결해준다. 그럼 당연히 길이가 5인 간선보다는, 3인 간선이 더 짧기
때문에 3번을 잇는 길이가 '3'인 간선을 선택하게 된다.
그렇게 되면 ? 위의 길이가 '3'인 간선 선택으로 인해서, '3번 정점'도 이제 선택된 정점이 된 것이다.
그림으로 보면 다음과 같아진다.
4. 가장 짧은 간선으로 연결되어 있는 정점을 선택하고, 정점들의 거리를 업데이트 한다.
- 가장 짧은 간선으로 연결되어 있는 정점을 우리는 이미 선택했다 (3번정점). 이렇게 되면, 거리를 업데이트 할 수 있는
정점들이 새로 생기게 된다. 바로 '4번정점' 과 '5번정점'의 거리가 업데이트가 될 수 있다.
그리고 이 부분을 생각할 때, 단순히 새로 추가된 '3번 정점'에서의 거리가 아닌, 1번 3번을 묶어놓은 곳 과의 거리로
생각하자.
정점들의 거리를 업데이트 할 때에는 위의 그림에서 빨강색으로 동그라미 쳐진 이미 선택된 정점들의 묶음 과의 거리
라고 생각하자.
그렇게 되면 Dist의 값이 아래와 같이 바뀌게 될 것이다.
5번은 어차피 3 ~ 4 번의 반복이라고 했으니, 다시 3번으로 돌아가보자.
3. 선택된 정점들과 연결되어 있는 간선들 중에서, 가장 짧은 길이의 간선을 선택해서 연결해준다.
- 아까 했던 것과 마찬가지로 간선들 중에서 가장 짧은 길이의 간선을 선택해보자.
위에서 말했지만, 다시 한번 말하자면, 이제부터는 빨간색 동그라미와 정점들을 연결해놓은 간선중에서
최단길이를 찾으면 된다.
그럼, 빨강색 동그라미와 정점 '4'번을 잇는 길이가 2인 간선이 선택될 것이다.
4. 가장 짧은 간선으로 연결되어 있는 정점을 선택하고, 정점들의 거리를 업데이트 한다.
- 이 상태에서, 거리를 업데이트 하게 되면 다음과 같이 변하게 된다.
다시 3번과정으로 돌아와서 가장 짧은 거리를 채택해보자. 그럼 빨간색 원과 '2'번정점을 잇는 길이가 1인 간선이
채택될 것이다.
이번 과정에서 거리의 업데이트는 발생하지 않았다. 다시 3번 과정으로 돌아와서 가장 짧은 거리를 채택하면,
빨간색 원과 '5'번 정점을 잇는 길이가 '4'인 간선이 채택될 것이다.
이 후, 마지막으로 '4'번 정점과 '6'번 정점을 잇는 길이가 5인 간선이 마지막으로 채택되게 될 것이다.
최종적으로 연결된 스패닝트리의 형태를 보면 다음과 같아진다.
이렇게 스패닝 트리를 구성하는 값이 총 15인 스패닝 트리가 생성된다.
그런데 우리가 그냥 넘어갔던 5번 과정을 보자.
5. 3 ~ 4 번의 과정은 N(전체 노드의 갯수) - 1번 만큼 반복해준다.
우리가 위에서 "현재 선택된 정점들과 연결된 간선 중, 최단길이의 간선을 뽑고, 정점들의 길이를 업데이트 시키는
과정"을 총 몇 번 했을까 ??
우리는 총 5번을 했다.
1. 1번 정점을 가장 처음에 선택했고, 3번 정점을 뽑고 거리 업데이트 1번.
2. 4번 정점을 뽑고 거리 업데이트 2번
3. 2번 정점을 뽑고 거리 업데이트 3번
4. 5번 정점을 뽑고 거리 업데이트 4번
5. 6번 정점을 뽑고 거리 업데이트 5번.
즉, 이 과정을 우리는 총 "전체 정점의 갯수 - 1 번만큼 진행"하게 된다.
'[ Algorithm ] > # Solution - ' 카테고리의 다른 글
| [ 다익스트라 알고리즘 ] 개념과 구현방법 (C++) (58) | 2020.03.04 |
|---|---|
| [ 프림 알고리즘 ] 개념과 구현방법(2) (C++) (6) | 2020.03.04 |
| [ 정렬 ] 정렬별 장단점 및 시간복잡도 (10) | 2019.04.30 |
| [ 정렬 ] 카운팅 정렬(Counting Sort) (C++) (0) | 2019.04.30 |
| [ 정렬 ] 기수 정렬 (Radix Sort) (C++) (4) | 2019.04.30 |