MST 2 - prim 의 알고리즘
Last updated
Last updated
공집합으로 초기화된 엣지들의 집합 A에 대하여 안전한 엣지들을 하나씩 추가하여 결과적으로는 MST 알고리즘에 대한 답을 찾는 과정이다.
안전한 엣지를 어떻게 찾는지에 대하여 kruskal 알고리즘과 차이가 있다.
prim의 알고리즘 역시 임의의 노드를 출발 노드로 선택을 한다.
출발 노드를 포함하는 트리를 점점 키워나간다.
kruscal 알고리즘에서는 엣지의 길이를 오름차순으로 정렬해서 그 순서대로 선택해나가기에 트리가 최초에는 연결되지 않은 모습을 띈다.
하지만 prim 알고리즘에서는 최초의 출발노드부터 트리를 조금씩 키워나가는 형태로 진행시킨다.
매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 엣지들 중 가장 가중치가 작은 엣지를 선택한다.
a부터 시작하여 엣지의 weight 가 최소인 것을 하나씩 선택한 위 트리 Va에 포함시켜나간다.
|Va| = n 이 되면 알고리즘은 종료된다.
prim 알고리즘에서 임의의 한 단계를 가정해본다.
A를 현재까지 알고리즘이 선택한 엣지의 집합이라고 하고, A를 포함하는 MST 가 존재한다고 가정해보자.
여기서 MST의 부분집합 A에 대하여 prim 알고리즘에 따라 고른 엣지를 하나 추가해도 여전히 MST의 부분집합이 될 수 있음을 증명하고자 한다.
아래의 그림에서 빨간선들을 Va에 속한 S라고 하고, 나머지 노드들을 V-S 라고 했을 때, 지금 상태는 서로 컷(S, V-S)을 이루며 존중하고 있는 상태가 된다. 이 컷을 가로지르는 엣지가 현재까지는 존재하지 않는다.
이때, prim 알고리즘에 의해 컷을 가로지르는 최소 가중치의 엣지를 골라 S와 연결한다고 해도, 여전히 MST를 위반하지 않게 된다.
만약 단순하고 직관적으로 접근하여 prim 의 알고리즘을 구현한다고 생각해보자. 시간복잡도는 O(n^3) 이다.
n개의 노드에 대하여 S 집단에 n/2 개, V-S 집단에 또다른 n/2 개의 노드가 있다고 해보자.
컷 (S, V-S) 를 잇는 노드의 개수는 최악의 경우, (2/n)^2 개가 된다. 즉, lightest edge 를 찾기 위한 탐색의 시간이 시간복잡도로 따지자면 O(n^2)이다.
여기에 모든 노드가 연결될 때까지 총 n-1번 이 연산을 반복해야하므로, 총 시간복잡도는 O(n^3)이 된다.
어떻게 더 나은 방법으로 구현할 수 있을까?
Va : 이미 트리에 포함된 노드들
Va에 아직 속하지 않은 각 노드 v에 대하여 다음과 같은 값을 유지한다.
key(v) : 이미 Va에 속한 노드와 자신을 연결하는 에지들 중에서 가중치가 최소인 에지 (u, v) 의 가중치
𝛑(v) : 그 에지 (u, v)의 끝점 u
장점
key 값이 최소인 노드를 찾는 식으로 바꿔 생각하면, 시간복잡도가 노드의 개수인 O(n) 으로 대폭 줄어들게 된다.
최초에는 출발점 - 모든 노드를 각각 비교하여 키와 파이값을 초기화 한다. 연결되지 않았다면 키값은 무한대, 파이값은 출발점 a로 둬버린다.
그리고 트리가 하나씩 연결될 때마다, 아직 연결되지 않은 다른 노드들의 키와 파이값을 갱신해주면 된다.
예를 들어 아까 상황에서 c-f 가 새롭게 연결되었다고 해보자. 이때, 새롭게 추가된 노드 f와 인접한 나머지 노드 d, e, g는 이 f와 연결된 엣지의 가중치값과 자신의 현재 key 값을 비교하여, key 값이 더 적을 때에만 갱신하도록 로직을 짤 수 있다.
이렇게 되면 prim 알고리즘의 시간복잡도는 다음과 같이 된다.
O(n) : 각 노드의 키값과 파이값을 갱신하는데 걸리는 시간
O(n) : 키값이 최소인 노드를 찾아 Va와 연결하는 시간
이 과정을 Va에 모든 노드가 들어갈 때까지 n-1번 반복한다.
따라서 O(n) + O(n) = O(n) 이고, O(n) * (n-1) = O(n^2) 이 된다. 이전의 O(n^3)에 비해서 획기적으로 줄어들었다.
r은 출발점
처음에는 모든 key들은 무한대로, 𝛑 들은 null 로 초기화를 한다.
출발점 r을 Va에 넣어준다.
key[r] 에는 0을 넣어준다.
이후에 Va에 모든 엣지들이 들어갈 때까지 반복해야하므로 n-1번 반복한다.
매 반복마다 키의 최소값을 찾고
해당 키를 가진 노드를 Va에 포함시켜준다.
그리고 해당 노드와 인접한 노드들에 대하여 키값과 파이값을 갱신해준다. 이때, 대상 노드와 연결된 엣지의 가중치를 현재 자신의 키값과 비교하여 업데이트 여부를 결정한다.
인접 행렬로 표현하나, 인접 리스트로 표현하나, 모두 똑같이 시간복잡도 O(n^2) 가 걸리게 된다.
최소 우선순위 큐를 사용하여 key 값이 최소인 노드를 찾는 로직을 개선할 수 있다.
V-Va에 속한 노드들을 저장한다.
extract-min : key 값이 최소인 노드를 삭제하고 반환한다.
key 값을 넣어놓은 queue 에서 최소값을 찾는 과정이 logn 시간이 소요된다.
연산 과정에서 key 값이 작은 값으로 변화가 발생하게 되므로 key 값을 업데이트 시켜준 뒤, 우선순위큐를 다시 min heap 구조로 맞추는 작업이 필요하다.
= 현재 key값보다 부모값이 크면 교체하는 과정을 반복하여 최소 값이 루트노드에 위치하도록 변경하는 작업
이 과정에서 소요되는 시간이 logn이다.
결국 이 알고리즘의 시간복잡도는
n-1 번 반복 * 최소값 찾는 시간 logn = nlogn
키값 비교하고 조정하는 시간 : sum of degree(v) * logn <= 엣지의 개수 m
즉, O(nlogn + mlogn) = O(mlogn) 이 된다.
이진 힙을 사용해서 우선순위 큐를 구현한 경우에는 위와 같이 O(mlogn), 우선순위 큐를 이용하지 않고 단순하게 구현할 경우, O(n^2) 가 된다.
fibonacci 힙을 사용해서 O(m+nlogn)에 구현하는 것도 가능하다.
