최소 신장 트리 - 프림 알고리즘

그래프 G=(V,E)에서 신장 트리는 정점 집합 V를 그대로 두고 간선을 |V| - 1개만 남겨 트리가 되도록 만든 것이다.

간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소 신장 트리라고 한다.

 

프림 알고리즘

집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워나간다.

맨 처음 정점을 제외하고는 정점을 하나 더할 때마다 간선이 하나씩 확정된다.

 

배열 d[]를 각 정점을 신장 트리에 포함시키는 비용을 구하는데 사용한다.

tree[v]는 정점 v를 신장 트리에 연결시키는 비용이 가장 적게 드는 간선을 저장한다.

 

1. 시작 정점 r의 연결 비용을 0으로, 나머지 정점들의 연결 비용을 무한대로 초기화한다.

2. 정점 r을 집합 S의 첫번째 원소로 포함시킨다. 그 후 r에 연결된 나머지 정점들을 살핀다. 그 정점들에 연결된 간선의 비용들을 d[]에 저장한다.

3. 최소 비용이 드는 정점을 새로 집합 S에 포함시킨다. 그 후 새로 포함된 정점에 연결된 다른 정점들의 비용도 업데이트 한다.

4. 모든 정점이 S에 포함될 때까지 3을 반복한다.

 

 

 

프림 알고리즘의 시간 분석

프림 알고리즘 시간 분석은 위에서 나온 방법으로 하는 것이 아닌 다른 방식으로 구현을 한 프림 알고리즘으로 분석을 할 것이다.

pseudo code

첫번째 for loop : |V|회 반복. O(V)

 

두번째 while loop : |V|회 반복.

 

deleteMin : 어떤 자료구조를 사용하느냐에 따라 시간이 달라짐.

만약 정렬된 배열로 유지한다면 가장 작은 원소 추출에는 상수 시간이 들겠지만 d[v]를 업데이트 할 때 배열을 한칸씩 줄줄이 이동시켜야하여 O(V)시간이 걸리게 됨. 최악의 경우 E번 일어날 수 있으므로 전체 시간은 O(VE).

정렬되지 않은 배열로 유지한다면 추출시 O(V)시간. 그러나 while문 때문에 총 시간은 O(V^2).

최소 힙 이용시 deleteMin()은 O(logV)시간에 가능. While loop 통틀어서는 O(VlogV). 그러나 d값 변동시 추가적으로 O(logV)시간이 소요되는데, 최악의 경우 E번 일어나므로 총 O(ElogV)

 

while문 안쪽에 있는 for loop : u와 인접한 간선만 훑으므로 while loop 통틀어 총 2E번을 돌게 된다. 결과적으로는 프림 알고리즘 시간에 영향을 미치지는 못함.

 

 

-> 최소 힙 이용시 O(ElogV)

 

 

 

 

출처 : 서울대학교 컴퓨터공학부 문병로 교수님 알고리즘 수업