[알고리즘] MST prim 이론(Eager version vs lazy version)

오늘은 Prim 알고리즘의 Eager version과 Lazy version의 비교를 하려고한다.

 

이러한 그래프가 있다고 하자. 

LAZY VERSION

Prim의 Lazy version은 모든 E(각 정점에서 발견된)를 다 우선순위 큐에 넣고, 하나씩 꺼내 쓴다. 그렇기 때문에, Lazy version은 O(ElogE)가 나오게 된다. 아래 그림에서 본다면, 지금 정점 0에서 연결된 Edges는 저기 표에 빨간색 글씨로 써져있는것이다. 그렇다면, key를 edge로 놓고, priority는 edge의 weight으로 해서 진행한다. pq에서 어떤 edge가 나왔을 경우, edge에 연결된 두 개의 정점을 visited인지 조사한다. 가장 작은 edges의 두 정점이 둘다 visited가 아니라면, 그것이 MST의 edge라고 할 수 있다. 그렇게된다면, 일단 2개의 정점을 visited라고 체크한다.

. 

1. 처음에 들어온 0에 대한 edge를 pq에 넣는다. 위의 그래프에서는 4개의 edge가 pq에 들어간다.여기서 가장 작은 0-7을 골라서 MST에 포함시키고 뺀다. 

0,7이 골라졌으니 7과 연결된 다른 edge를 pq에 추가한다. pq니깐 weight이 가장 작은 1-7이 맨 위로 올라오게 된다. 우리는 이제 1-7을 골라서 MST에 포함시킨다.

1이 포함되었기 때문에, 1과 연결된 edge를 다 pq에 넣는다. 그리고 맨 위로 올라오는것은 0-2이다.

0-2가 골라졌으니, 이제 2와 연결된 edges를 찾는데, 2-7과 1-2는 이미 방문되었기에 넣지 않는다. 그리고 2-3이 가장 작으니 이 edge를 MST에 추가한다.

EAGER VERSION

Eager version은 우선순위큐(pq)를 사용하는데, vertices를 기준으로 우선순위 큐를 사용한다. 위의 상황에서 0과 인접 정점은 4, 7, 2, 이다. 그래서 여기서 가장 짧은 weight인 0-7, 즉 정점 7을 선택한다. 그렇다면, 현재 7과 연결된 정점이 4, 2, 1, 5가 존재한다. 하지만 다시 생각해본다면, 우리는 pq를 정점을 기준으로 운용하고 있고, 아까 4와 2가 들어와있었다. 그렇다면, 0-2, 0-4와 7-4, 7-2의 weight을 비교해서 더 짧은 값으로 갱신해준다. (이에 대한 해결법은 위의 게시물에서 찾을 수 있다.)그렇게 해서 계속 갱신되는 값은 다음과 같게 변한다. 1에서 가장 짧은 edge는 1-7이고 7은 0-7이고, 이렇게 쭈욱 나아간다.

시간복잡도를 살펴보자면, O(ElogV)이다. 일단 왜냐면 우리는 정점들을 pq에 넣기 때문에 O(logV)가 발생한다. 또한 우리는 가장 작은 정점을 pq에서 뺄 것이기 때문에 O(logV)가 발생한다. pq에서 decrease-key를 하는 것은 pq에서 dist가 감소하면, 다시 heapify를 하는 과정이다. 이 과정 역시 O(logV)이다. 하지만 decrease-key할때 모든 E를 확인은 하기 때문에, 즉, 정점에 달린 E를 확인은 해보기 때문에 O(E)가 발생한다고 볼 수 있다. 따라서 O(ElogV)라고 생각할 수 있다.

1단계 : 시작점이 0일때, 인접 정점 4개를 기준으로 pq에 weight과 함께 집어넣는다.

2단계 : 정점 7이 골라졌다. 그렇다면 정점 7과 연결된 다른 정점 1, 5, 4, 2에 대한 weight을 계속 갱신 시켜준다. 정점 1에 대한 내용은 없었다.(한번에 갈수 있는 정점이 아니었다.) 7을 포함시키면서 1에 직접 갈수 있게 되어서, 1 정점에 대한 weight을 추가한다. 5 역시 마찬가지이다. 정점 4의 경우는 4-7과 0-4를 비교해서 짧은 값을 남겨 놓으면 된다. 

 

3단계 4단계도 이런방식으로 나아가다 보면 아래 처럼 edgeTo[] 와, distTo[] 가 나오게 된다.