최소 신장 트리
28 Nov 2017 | Minimum Spanning Tree Graph
이번 글에서는 최소신장트리(Minimum Spanning Tree, MST)를 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
신장트리(Spanning Tree)란 (1) 원 그래프의 모든 노드를 포함하고 (2) 모든 노드가 서로 연결되어 있으면서 (3) 트리(Tree)의 속성을 만족하는 그래프를 가리킵니다. 예컨대 하단 좌측과 같은 원 그래프의 스패닝트리는 하단 우측과 같이 총 8개의 스패닝트리들을 가질 수 있습니다.
최소신장트리(MST)는 가능한 신장트리 가운데 엣지 가중치의 합이 최소인 신장트리를 말합니다. 예컨대 하단 좌측과 같은 원 그래프의 MST는 하단 우측과 같습니다.
MST는 노드 간 연결성을 보장하면서 노드 사이를 잇는 거리/비용 등을 최소로 하는 그래프를 의미하기 때문에 응용 범위가 넓습니다. 이 글에서는 원 그래프에서 MST를 찾아내는 기법인 크루스칼 알고리즘(Kruskal’s algorithm)과 프림 알고리즘(Prim’s algorithm)을 살펴보도록 하겠습니다.
크루스칼 알고리즘
크루스칼 알고리즘은 분석 대상 노드에 연결된 엣지 가운데 가중치가 최소인 엣지를 고르되, 이렇게 추가된 엣지로 그래프가 트리 속성이 깨지지 않는지 여부를 체크하는 방식으로 작동합니다. 이때 가중치가 최소인 엣지를 light edge, 추가 엣지로도 트리 속성을 만족하고 있다면 해당 엣지를 safe하다고 합니다. 요컨대 크루스칼 알고리즘은 safe하고 light한 엣지를 반복적으로 찾아가는 기법입니다. 크루스칼 알고리즘의 작동 방식을 예시와 함께 보도록 하겠습니다.
크루스칼 알고리즘은 디스조인트 셋(disjoint set)을 기본 자료구조로 활용합니다. (a)와 같이 주어진 그래프가 있다고 칩시다. 우선 모든 노드에 대해 make-set 연산을 수행합니다. 이후 모든 엣지를 가중치를 기준으로 오름차순 정렬합니다. 결과(MST)로 반환할 $A$는 공집합으로 초기화해 둡니다. 크루스칼 알고리즘은 가중치가 가장 작은 엣지부터 분석하기 때문에 시작노드를 별도로 설정하지 않습니다.
(a)를 보겠습니다. 그래프 모든 엣지 가운데 가중치가 최소(1)인 ($h,g$)가 분석 대상입니다. $h$와 $g$가 서로 다른 셋(find 연산으로 확인)이기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($h,g$)를 추가하고 $h$가 속한 셋과 $g$가 속한 셋을 합칩니다(Union 연산).
(b)를 봅시다. 남은 엣지 가운데 가중치가 최소(2)인 ($i,c$)가 분석 대상입니다. $i$와 $c$가 서로 다른 셋이기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($i,c$)를 추가하고 $i$가 속한 셋과 $c$가 속한 셋을 합칩니다.
(c)를 봅시다. 남은 엣지 가운데 가중치가 최소(2)인 ($g,f$)가 분석 대상입니다. $g$가 속한 셋과 $f$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($g,f$)를 추가하고 $g$가 속한 셋과 $f$가 속한 셋을 합칩니다.
(d)를 봅시다. 남은 엣지 가운데 가중치가 최소(4)인 ($a,b$)가 분석 대상입니다. $a$가 속한 셋과 $b$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($a,b$)를 추가하고 $a$가 속한 셋과 $b$가 속한 셋을 합칩니다.
(e)를 봅시다. 남은 엣지 가운데 가중치가 최소(4)인 ($c,f$)가 분석 대상입니다. $c$가 속한 셋과 $f$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($c,f$)를 추가하고 $c$가 속한 셋과 $f$가 속한 셋을 합칩니다.
(f)를 봅시다. 남은 엣지 가운데 가중치가 최소(6)인 ($i,g$)가 분석 대상입니다. $i$가 속한 셋과 $g$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 바꿔 말해 사이클(cycle)이 존재한다는 이야기입니다. 따라서 ($i,g$)는 건너 뜁니다.
(g)를 봅시다. 남은 엣지 가운데 가중치가 최소(7)인 ($c,d$)가 분석 대상입니다. $c$가 속한 셋과 $d$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($c,d$)를 추가하고 $c$가 속한 셋과 $d$가 속한 셋을 합칩니다.
(h)를 봅시다. 남은 엣지 가운데 가중치가 최소(7)인 ($i,h$)가 분석 대상입니다. $i$가 속한 셋과 $h$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 따라서 ($i,h$)는 건너 뜁니다.
(i)를 봅시다. 남은 엣지 가운데 가중치가 최소(8)인 ($a,h$)가 분석 대상입니다. $a$가 속한 셋과 $h$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($a,h$)를 추가하고 $a$가 속한 셋과 $h$가 속한 셋을 합칩니다.
(j)를 봅시다. 남은 엣지 가운데 가중치가 최소(8)인 ($b,c$)가 분석 대상입니다. $b$가 속한 셋과 $c$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 따라서 ($b,c$)는 건너 뜁니다.
(k)를 봅시다. 남은 엣지 가운데 가중치가 최소(9)인 ($d,e$)가 분석 대상입니다. $d$가 속한 셋과 $e$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($d,e$)를 추가하고 $d$가 속한 셋과 $e$가 속한 셋을 합칩니다.
(l)을 봅시다. 남은 엣지 가운데 가중치가 최소(10)인 ($e,f$)가 분석 대상입니다. $e$가 속한 셋과 $f$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 따라서 ($e,f$)는 건너 뜁니다.
(m)을 봅시다. 남은 엣지 가운데 가중치가 최소(11)인 ($b,h$)가 분석 대상입니다. $b$가 속한 셋과 $h$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 따라서 ($b,h$)는 건너 뜁니다.
(n)을 봅시다. 남은 엣지 가운데 가중치가 최소(14)인 ($d,f$)가 분석 대상입니다. $d$가 속한 셋과 $f$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 따라서 ($d,f$)는 건너 뜁니다.
모든 엣지에 대해 분석을 마쳤으므로 크루스칼 알고리즘 수행을 종료합니다. 크루스칼 알고리즘의 의사코드는 다음과 같습니다.
크루스칼 알고리즘의 계산복잡성을 따져보겠습니다. 모든 노드에 대해 Make-Set 연산을 수행하므로 초기화에 필요한 계산량은 $O(V)$입니다. 이후 엣지를 중심으로 정렬을 수행하므로 현존하는 알고리즘 가운데 가장 성능 좋은 기법을 쓸 경우 그 계산량은 $O(E\lg{E})$입니다.
이제 반복문을 보겠습니다. 셋에 속한 데이터 수가 $n$개일 때 Find-Set , Union 연산의 계산복잡성은 모두 $O(\lg{n})$이고, 이를 전체 엣지에 대해 반복 수행하므로 반복문에서 필요한 계산량은 $O(E\lg{E})$입니다. 따라서 크루스칼 알고리즘의 전체적인 계산복잡성은 $O(E\lg{E})$가 됩니다.
프림 알고리즘
프림 알고리즘은 solution set과 non-solution set 사이를 연결하는 엣지 가운데 가중치가 가장 작은 엣지를 하나 뽑고 이 엣지에 연결된 노드와 해당 엣지를 solution set에 넣습니다. 아래 그림에서는 $v$와 ($u,v$)를 $S$에 집어넣는다고 보시면 됩니다.
이를 solution set에 모든 노드가 포함될 때까지 반복수행하면 프림 알고리즘이 종료됩니다. 프림 알고리즘을 예시와 함께 살펴보도록 하겠습니다.
(a)와 같은 그래프가 주어졌을 때 우선 자료구조를 초기화합니다. (a)를 먼저 보겠습니다. 노드 $a$에 연결된 엣지 가운데 가중치가 4로 가장 작은 엣지 ($a,b$)를 선택합니다. (b)와 같습니다.
(c)를 보겠습니다. (b)에서 선택한 엣지와 관계 있는 노드 {$a,b$}에 연결된 엣지들 가운데 가중치가 8로 가장 작은 ($b,c$)를 선택합니다.
(d)를 보겠습니다. (a)와 (b)에서 선택한 엣지와 관계 있는 노드 {$a,b,c$}에 연결된 엣지들 가운데 가중치가 2로 가장 작은 엣지 ($c,i$)를 선택합니다.
(e)를 보겠습니다. {$a,b,c,i$}에 연결된 엣지들 가운데 가중치가 4로 가장 작은 엣지 ($c,f$)를 선택합니다. (f)에서는 {$a,b,c,f,i$}에 연결된 엣지들 가운데 가중치가 2로 가장 작은 엣지 ($g,f$)를 선택합니다.
(g)에서는 {$a,b,c,f,g,i$}에 연결된 엣지들 가운데 가중치가 1로 가장 작은 엣지 ($g,h$)를 선택합니다. (h)에서는 {$a,b,c,f,g,h,i$}에 연결된 엣지들 가운데 가중치가 7로 가장 작은 엣지 ($c,d$)를 선택합니다. 여기서 주의할 점은 ($h,i$) 또한 그 가중치가 7로 연결되지 않은 엣지 가운데 가장 작은 것은 맞지만, 노드 $h$와 $i$ 모두 이미 선택된 노드들이므로 해당 엣지는 선택에서 배제된다는 것입니다.
(i)에서는 {$a,b,c,d,f,g,h,i$}에 연결된 엣지들 가운데 가중치가 9로 가장 작은 엣지 ($d,e$)를 선택합니다. 이로써 모든 노드가 MST로 선택됐으므로 프림 알고리즘 수행을 종료합니다.
프림 알고리즘의 의사코드는 다음과 같습니다.
프림 알고리즘의 계산복잡성을 따져보겠습니다. 여기서는 최대/최소값을 찾는 데 효율적인 힙(heap)을 쓴다고 가정해 보겠습니다. 위 의사코드에서 u.key란 노드 $u$에 연결된 엣지 가중치의 최소값이며 u.π란 노드 $u$의 부모노드를 가리킵니다.
우선 모든 노드를 초기화(non-solution set $Q$에 모든 노드 삽입 등)하는 데 $O($|$V$|$)$만큼의 계산복잡성이 듭니다. 모든 노드 가운데 key값이 가장 작은 걸 뽑아내는 extract-MIN 연산을 하려면 힙의 말단 노드가 루트 노드까지 자리 이동을 해야 하므로 트리의 높이에 상당하는 $O(lg{V})$만큼의 계산이 필요합니다.
decrease-KEY(Q, v, w(v,u)) 연산은 노드 $v$의 부모노드가 $u$가 되도록 하고, $v$의 key값(=$v$에 연결된 엣지 가중치의 최소값)을 ($u,v$)의 가중치로 업데이트하는 걸 가리킵니다. 힙의 키값을 업데이트하려면 최대 트리의 높이에 상당하는 탐색을 해야 하므로 $O(\lg{V})$만큼의 계산이 필요합니다. 이것을 노드 $u$에 연결된 엣지 수(그 기대값은 $E/V$)만큼 수행해야 하므로 decrease-KEY 연산은 $O(E/V\lg{V})$만큼의 계산이 필요합니다.
extract-MIN과 decrease-KEY 연산은 모든 노드에 대해 반복 수행(non-solution set $Q$가 공집합이 될 때까지)해야 하므로 프림 알고리즘의 전체적인 계산복잡성은 $O((V+E)\lg{V})$가 됩니다.
이번 글에서는 최소신장트리(Minimum Spanning Tree, MST)를 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
신장트리(Spanning Tree)란 (1) 원 그래프의 모든 노드를 포함하고 (2) 모든 노드가 서로 연결되어 있으면서 (3) 트리(Tree)의 속성을 만족하는 그래프를 가리킵니다. 예컨대 하단 좌측과 같은 원 그래프의 스패닝트리는 하단 우측과 같이 총 8개의 스패닝트리들을 가질 수 있습니다.
최소신장트리(MST)는 가능한 신장트리 가운데 엣지 가중치의 합이 최소인 신장트리를 말합니다. 예컨대 하단 좌측과 같은 원 그래프의 MST는 하단 우측과 같습니다.
MST는 노드 간 연결성을 보장하면서 노드 사이를 잇는 거리/비용 등을 최소로 하는 그래프를 의미하기 때문에 응용 범위가 넓습니다. 이 글에서는 원 그래프에서 MST를 찾아내는 기법인 크루스칼 알고리즘(Kruskal’s algorithm)과 프림 알고리즘(Prim’s algorithm)을 살펴보도록 하겠습니다.
크루스칼 알고리즘
크루스칼 알고리즘은 분석 대상 노드에 연결된 엣지 가운데 가중치가 최소인 엣지를 고르되, 이렇게 추가된 엣지로 그래프가 트리 속성이 깨지지 않는지 여부를 체크하는 방식으로 작동합니다. 이때 가중치가 최소인 엣지를 light edge, 추가 엣지로도 트리 속성을 만족하고 있다면 해당 엣지를 safe하다고 합니다. 요컨대 크루스칼 알고리즘은 safe하고 light한 엣지를 반복적으로 찾아가는 기법입니다. 크루스칼 알고리즘의 작동 방식을 예시와 함께 보도록 하겠습니다.
크루스칼 알고리즘은 디스조인트 셋(disjoint set)을 기본 자료구조로 활용합니다. (a)와 같이 주어진 그래프가 있다고 칩시다. 우선 모든 노드에 대해 make-set 연산을 수행합니다. 이후 모든 엣지를 가중치를 기준으로 오름차순 정렬합니다. 결과(MST)로 반환할 $A$는 공집합으로 초기화해 둡니다. 크루스칼 알고리즘은 가중치가 가장 작은 엣지부터 분석하기 때문에 시작노드를 별도로 설정하지 않습니다.
(a)를 보겠습니다. 그래프 모든 엣지 가운데 가중치가 최소(1)인 ($h,g$)가 분석 대상입니다. $h$와 $g$가 서로 다른 셋(find 연산으로 확인)이기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($h,g$)를 추가하고 $h$가 속한 셋과 $g$가 속한 셋을 합칩니다(Union 연산).
(b)를 봅시다. 남은 엣지 가운데 가중치가 최소(2)인 ($i,c$)가 분석 대상입니다. $i$와 $c$가 서로 다른 셋이기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($i,c$)를 추가하고 $i$가 속한 셋과 $c$가 속한 셋을 합칩니다.
(c)를 봅시다. 남은 엣지 가운데 가중치가 최소(2)인 ($g,f$)가 분석 대상입니다. $g$가 속한 셋과 $f$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($g,f$)를 추가하고 $g$가 속한 셋과 $f$가 속한 셋을 합칩니다.
(d)를 봅시다. 남은 엣지 가운데 가중치가 최소(4)인 ($a,b$)가 분석 대상입니다. $a$가 속한 셋과 $b$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($a,b$)를 추가하고 $a$가 속한 셋과 $b$가 속한 셋을 합칩니다.
(e)를 봅시다. 남은 엣지 가운데 가중치가 최소(4)인 ($c,f$)가 분석 대상입니다. $c$가 속한 셋과 $f$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($c,f$)를 추가하고 $c$가 속한 셋과 $f$가 속한 셋을 합칩니다.
(f)를 봅시다. 남은 엣지 가운데 가중치가 최소(6)인 ($i,g$)가 분석 대상입니다. $i$가 속한 셋과 $g$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 바꿔 말해 사이클(cycle)이 존재한다는 이야기입니다. 따라서 ($i,g$)는 건너 뜁니다.
(g)를 봅시다. 남은 엣지 가운데 가중치가 최소(7)인 ($c,d$)가 분석 대상입니다. $c$가 속한 셋과 $d$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($c,d$)를 추가하고 $c$가 속한 셋과 $d$가 속한 셋을 합칩니다.
(h)를 봅시다. 남은 엣지 가운데 가중치가 최소(7)인 ($i,h$)가 분석 대상입니다. $i$가 속한 셋과 $h$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 따라서 ($i,h$)는 건너 뜁니다.
(i)를 봅시다. 남은 엣지 가운데 가중치가 최소(8)인 ($a,h$)가 분석 대상입니다. $a$가 속한 셋과 $h$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($a,h$)를 추가하고 $a$가 속한 셋과 $h$가 속한 셋을 합칩니다.
(j)를 봅시다. 남은 엣지 가운데 가중치가 최소(8)인 ($b,c$)가 분석 대상입니다. $b$가 속한 셋과 $c$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 따라서 ($b,c$)는 건너 뜁니다.
(k)를 봅시다. 남은 엣지 가운데 가중치가 최소(9)인 ($d,e$)가 분석 대상입니다. $d$가 속한 셋과 $e$가 속한 셋이 서로 다르기 때문에 트리 속성을 만족(safe)합니다. 따라서 $A$에 분석 대상 엣지 ($d,e$)를 추가하고 $d$가 속한 셋과 $e$가 속한 셋을 합칩니다.
(l)을 봅시다. 남은 엣지 가운데 가중치가 최소(10)인 ($e,f$)가 분석 대상입니다. $e$가 속한 셋과 $f$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 따라서 ($e,f$)는 건너 뜁니다.
(m)을 봅시다. 남은 엣지 가운데 가중치가 최소(11)인 ($b,h$)가 분석 대상입니다. $b$가 속한 셋과 $h$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 따라서 ($b,h$)는 건너 뜁니다.
(n)을 봅시다. 남은 엣지 가운데 가중치가 최소(14)인 ($d,f$)가 분석 대상입니다. $d$가 속한 셋과 $f$가 속한 셋이 서로 같기 때문에 트리 속성을 만족하지 않습니다. 따라서 ($d,f$)는 건너 뜁니다.
모든 엣지에 대해 분석을 마쳤으므로 크루스칼 알고리즘 수행을 종료합니다. 크루스칼 알고리즘의 의사코드는 다음과 같습니다.
크루스칼 알고리즘의 계산복잡성을 따져보겠습니다. 모든 노드에 대해 Make-Set 연산을 수행하므로 초기화에 필요한 계산량은 $O(V)$입니다. 이후 엣지를 중심으로 정렬을 수행하므로 현존하는 알고리즘 가운데 가장 성능 좋은 기법을 쓸 경우 그 계산량은 $O(E\lg{E})$입니다.
이제 반복문을 보겠습니다. 셋에 속한 데이터 수가 $n$개일 때 Find-Set , Union 연산의 계산복잡성은 모두 $O(\lg{n})$이고, 이를 전체 엣지에 대해 반복 수행하므로 반복문에서 필요한 계산량은 $O(E\lg{E})$입니다. 따라서 크루스칼 알고리즘의 전체적인 계산복잡성은 $O(E\lg{E})$가 됩니다.
프림 알고리즘
프림 알고리즘은 solution set과 non-solution set 사이를 연결하는 엣지 가운데 가중치가 가장 작은 엣지를 하나 뽑고 이 엣지에 연결된 노드와 해당 엣지를 solution set에 넣습니다. 아래 그림에서는 $v$와 ($u,v$)를 $S$에 집어넣는다고 보시면 됩니다.
이를 solution set에 모든 노드가 포함될 때까지 반복수행하면 프림 알고리즘이 종료됩니다. 프림 알고리즘을 예시와 함께 살펴보도록 하겠습니다.
(a)와 같은 그래프가 주어졌을 때 우선 자료구조를 초기화합니다. (a)를 먼저 보겠습니다. 노드 $a$에 연결된 엣지 가운데 가중치가 4로 가장 작은 엣지 ($a,b$)를 선택합니다. (b)와 같습니다.
(c)를 보겠습니다. (b)에서 선택한 엣지와 관계 있는 노드 {$a,b$}에 연결된 엣지들 가운데 가중치가 8로 가장 작은 ($b,c$)를 선택합니다.
(d)를 보겠습니다. (a)와 (b)에서 선택한 엣지와 관계 있는 노드 {$a,b,c$}에 연결된 엣지들 가운데 가중치가 2로 가장 작은 엣지 ($c,i$)를 선택합니다.
(e)를 보겠습니다. {$a,b,c,i$}에 연결된 엣지들 가운데 가중치가 4로 가장 작은 엣지 ($c,f$)를 선택합니다. (f)에서는 {$a,b,c,f,i$}에 연결된 엣지들 가운데 가중치가 2로 가장 작은 엣지 ($g,f$)를 선택합니다.
(g)에서는 {$a,b,c,f,g,i$}에 연결된 엣지들 가운데 가중치가 1로 가장 작은 엣지 ($g,h$)를 선택합니다. (h)에서는 {$a,b,c,f,g,h,i$}에 연결된 엣지들 가운데 가중치가 7로 가장 작은 엣지 ($c,d$)를 선택합니다. 여기서 주의할 점은 ($h,i$) 또한 그 가중치가 7로 연결되지 않은 엣지 가운데 가장 작은 것은 맞지만, 노드 $h$와 $i$ 모두 이미 선택된 노드들이므로 해당 엣지는 선택에서 배제된다는 것입니다.
(i)에서는 {$a,b,c,d,f,g,h,i$}에 연결된 엣지들 가운데 가중치가 9로 가장 작은 엣지 ($d,e$)를 선택합니다. 이로써 모든 노드가 MST로 선택됐으므로 프림 알고리즘 수행을 종료합니다.
프림 알고리즘의 의사코드는 다음과 같습니다.
프림 알고리즘의 계산복잡성을 따져보겠습니다. 여기서는 최대/최소값을 찾는 데 효율적인 힙(heap)을 쓴다고 가정해 보겠습니다. 위 의사코드에서 u.key란 노드 $u$에 연결된 엣지 가중치의 최소값이며 u.π란 노드 $u$의 부모노드를 가리킵니다.
우선 모든 노드를 초기화(non-solution set $Q$에 모든 노드 삽입 등)하는 데 $O($|$V$|$)$만큼의 계산복잡성이 듭니다. 모든 노드 가운데 key값이 가장 작은 걸 뽑아내는 extract-MIN 연산을 하려면 힙의 말단 노드가 루트 노드까지 자리 이동을 해야 하므로 트리의 높이에 상당하는 $O(lg{V})$만큼의 계산이 필요합니다.
decrease-KEY(Q, v, w(v,u)) 연산은 노드 $v$의 부모노드가 $u$가 되도록 하고, $v$의 key값(=$v$에 연결된 엣지 가중치의 최소값)을 ($u,v$)의 가중치로 업데이트하는 걸 가리킵니다. 힙의 키값을 업데이트하려면 최대 트리의 높이에 상당하는 탐색을 해야 하므로 $O(\lg{V})$만큼의 계산이 필요합니다. 이것을 노드 $u$에 연결된 엣지 수(그 기대값은 $E/V$)만큼 수행해야 하므로 decrease-KEY 연산은 $O(E/V\lg{V})$만큼의 계산이 필요합니다.
extract-MIN과 decrease-KEY 연산은 모든 노드에 대해 반복 수행(non-solution set $Q$가 공집합이 될 때까지)해야 하므로 프림 알고리즘의 전체적인 계산복잡성은 $O((V+E)\lg{V})$가 됩니다.
Comments