[Algorithm] 프림(Prim) 알고리즘

이번 포스팅에서는 프림(Prim) 알고리즘에 대해서 알아보겠습니다.

1.프림(Prim) 알고리즘이란?

정의

: 프림(Prim) 알고리즘은 최소 비용 신장 트리(Minimum Spanning Tree, MST)를 찾는 그래프 알고리즘 중 하나입니다. 그래프의 모든 정점을 연결하면서 가장 적은 비용을 들이는 트리를 구성하는 것이 목표입니다.

최소 비용 신장 트리는 그래프 내의 모든 정점을 포함하면서 사이클이 없는 트리입니다. 즉, 모든 정점을 연결하면서 불필요한 간선을 제거하여 비용을 최소화하는 트리를 의미합니다.

2. 프림(Prim) 알고리즘

프림 알고리즘은 MST를 찾기 위한 그리디 패러다임의 알고리즘입니다. 이 알고리즘을 따라가면 최소 스패닝 트리를 구할 수 있습니다.

step 0 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )

step 1 T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

step 2 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다. (step 1에서 찾은 간선도 같이 T에 포함됩니다.)

step 3 모든 노드가 T 에 포함될 때 까지, 1,2 를 반복한다.

이 알고리즘을 통해 만들어진 최후의 T는 MST가 됩니다. 아래의 그래프에 프림 알고리즘을 순서대로 적용 시켜 보겠습니다. 편의 상, T에 포함된 노드는 빨간색, T에 아직 포함되지 않은 노드는 파란색으로 표시하겠습니다.

step 0 임의의 정점을 선택하여 비어있는 T에 포함시킨다. (이제 T는 노드가 한 개인 트리. )

-> 초기 상태는 T에 아무것도 포함되어 있지 않습니다. 임의의 정점으로는 아무거나 선택해도 상관없지만, 예시에서는 1을 선택하겠습니다.

step 1 T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

-> 빨간색과 파란색을 연결하는 간선 중 가중치가 최소인 걸 찾으면 됩니다. 노드 1과 노드 3을 연결한 가중치 4의 간선이 최선입니다.

step 2 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다. -> 노드 3을 T 에 포함시킵니다.

step 1 T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다. -> 노드 2과 노드 3을 연결한 가중치 2의 간선이 최선입니다.

step 2 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다. -> 노드 2을 T 에 포함시킵니다.

step 1 T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다. -> 노드 3과 노드 4을 연결한 가중치 6의 간선이 최선입니다.

step 2 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다. -> 노드 4을 T 에 포함시킵니다.

step 1 T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다. -> 노드 4과 노드 5을 연결한 가중치 3의 간선이 최선입니다.

step 2 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다. -> 노드 5을 T 에 포함시킵니다.

step 1 T 에 있는 노드와 T 에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다. -> 노드 4과 노드 6을 연결한 가중치 8의 간선이 최선입니다.

step 2 찾은 간선이 연결하는 두 노드 중, T 에 없던 노드를 T에 포함시킨다. -> 노드 6을 T 에 포함시킵니다.

이렇게 간선이 가중치의 합이 23인 트리가 완성되었으며, 이 트리가 그래프의 MST 입니다. 이러한 프림 알고리즘을 구현하는 데에는 2가지 방법이 있습니다.

방법 1은 배열을 사용하여, T 와 각 노드를 연결하는 최소 간선 가중치를 찾는 방법이며 시간 복잡도는 O(V^2) 입니다.

방법 2는 힙 ( min heap ) 을 사용해 최소의 간선 가중치를 찾는 방법이며, 시간 복잡도는 O(E log E), 즉, O(E log V) 입니다. V = 정점의 개수, E = 간선의 개수