Advanced Algorithm - MST(Improved Prim's Algorithm)(6)

1. 개선된 프림 알고리즘이란? 

- 기존의 프림 알고리즘에서 파생된 알고리즘으로, 개선된 프림 알고리즘은 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식이다. 그렇다면 무엇이 개선되었을까? 

 

- 이전 포스팅에서 다뤘던 기본적인 프림 알고리즘은 간선을 기준으로, 간선의 개수에 따른 while문의 반복회수를 측정하여 E log E 만큼의 시간복잡도를 갖는다.

 

- 이와는 다르게, 개선된 프림 알고리즘은 노드를 기준으로 하여 E log V 만큼의 시간복잡도를 갖는다. 그래프는 노드의 수 보다 간선의 수가 더 많기 때문에 그 차이만큼 반복회수가 줄어들어 알고리즘의 시간복잡도가 개선됨을 의미한다.

---

2. 개선된 프림 알고리즘의 로직 

- 개선된 프림 알고리즘은 노드마다 key값을 갖고 있는 것이 특징이다. 로직은 다음과 같다. 

 

1) 초기화 - 정점(노드)에 key값을 부여하는 구조를 만들어, 최초에 선택된 노드의 key값에 0을 부여하고 나머지 노드에는 무한대(inf)를 부여한다. 모든 정점의 key값은 우선순위 큐에 저장한다. 

 

2) extract min 로직 - 가장 key값이 작은 정점(최초 선택된 노드)을 추출(pop)한다.

 

 - a) 추출된 정점과 인접한 노드의 key값(inf)과 간선이 갖는 가중치를 비교하여 가중치가 인접한 노드의 key값(inf)보다 작다면, 해당 인접노드의 key값을 해당 간선의 가중치로 갱신(update)한다. 반대의 경우는 스킵(skip)한다. 

 

 - b) 가장 작은 key값으로 선택된 노드는 MST에 저장된다. 

 

3) decrease key 로직 - 인접노드의 key값 갱신시, 우선순위 큐는 최소 key값을 가지는 노드를 루트노드로 올려 재구성한다.

 

4) 2번, 3번 과정을 반복하여 MST를 완성한다. 

 

 

* 개선된 프림 알고리즘 구현시 고려사항

- 우선순위 큐(최소힙) 구조에서, 이미 들어가 있는 데이터의 값 변경시, 최소값을 가지는 데이터를 루트노드로 올려놓도록 재구성하는 기능이 필요하다.

 

- 구현 복잡도를 줄이기 위해, heapdict 라이브러리를 통해, 해당 기능을 간단히 구현

---

3. 개선된 프림 알고리즘 코드구현 

a) 기본 그래프 구현 

기본 그래프

mygraph = {
    # ex) A노드에서 B노드로 가는 간선의 가중치는 7 
    # ex) A노드에서 D노드로 가는 간선의 가중치는 5
    'A': {'B': 7, 'D': 5},
    'B': {'A': 7, 'D': 9, 'C': 8, 'E': 7},
    'C': {'B': 8, 'E': 5},
    'D': {'A': 5, 'B': 9, 'E': 7, 'F': 6},
    'E': {'B': 7, 'C': 5, 'D': 7, 'F': 8, 'G': 9},
    'F': {'D': 6, 'E': 8, 'G': 11},
    'G': {'E': 9, 'F': 11}    
}
mst, total_weight = prim(mygraph, 'A')
print ('MST:', mst)
print ('Total Weight:', total_weight)

 

 

 

b) 알고리즘 구현

from heapdict import heapdict

def prim(graph, start):
    
    mst = list()
    
    # heapdict() 함수를 사용하면 최소힙 자료구조를 생성한다.
    # 최소힙 - 가장 작은값이 루트노드가 되는 자료구조
    # 이로써, 개선된 프림 알고리즘 로직(3)의 과정이 생략된다. 
    keys = heapdict() 
    
    # key값을 업데이트 할 때, 어느 노드를 기준으로
    # 해당 노드의 key값이 갱신되었는지 알기위한 자료구조 
    # ex) A노드를 시작(기준)으로 B 노드의 key값이 업데이트 된 경우, pi['B'] = 'A'
    pi = dict() 
    
    # 총 가중치를 저장하기 위한 변수 
    total_weight = 0
    
    # 개선된 프림 알고리즘 로직(1)
    for node in graph.keys():
        keys[node] = float('inf')
        pi[node] = None
    keys[start], pi[start] = 0, start

    while keys:
        # 개선된 프림 알고리즘 로직(2)
        # 생략된 3번 과정이 popitem() 함수에서 수행된다. 
        current_node, current_key = keys.popitem()
        
        # 개선된 프림 알고리즘 로직(2 - b)
        mst.append([pi[current_node], current_node, current_key])
        total_weight += current_key
        
        # 개선된 프림 알고리즘 로직(2 - a)
        for adjacent, weight in mygraph[current_node].items():    
            if adjacent in keys and weight < keys[adjacent]:
                keys[adjacent] = weight
                pi[adjacent] = current_node
                
    return mst, total_weight

 

[테스트 결과]

---

3. 개선된 프림 알고리즘의 시간복잡도

- 일반적인 heap 자료 구조 자체에는 decrease key 로직은 존재하지 않는다. 하지만, heapdict 라이브러리를 사용하여 손쉽게 구현할 수 있다. 

 

*decrease key 로직 - heap 내부의 데이터 우선순위 변경시, 최소 우선순위 데이터를 루트노드로 만들어주는 로직

 

- 개선된 프림 알고리즘의 시간복잡도는 다음과 같이 계산할 수 있다.

 

1) 최초 key 생성 시간복잡도(초기화 부분) = O(V)

 

2) while 구문과 keys.popitem()의 시간복잡도 = O(V log V) 

• while 구문은 V(노드 갯수)번 실행 = O(V)

• heap 에서 최소 key 값을 가지는 노드 정보 추출 시(pop)의 시간 복잡도 = O(logV)

3) for 구문의 총 시간복잡도 = O(ElogV)

• for 구문은 while 구문 반복할 때마다 최대 간선의 수 E만큼 실행 = O(E)
• for 구문 안에서 key값을 갱신할 때마다 heap 구조를 변경해야 하며, heap 에는 최대 V개의 정보가 있으므로 O(logV)

 

- 위의 계산을 종합해보면, 개선된 프림 알고리즘의 시간 복잡도는 O(V+VlogV+ElogV) 이다. 하지만, 아래와 같은 이유로 

• O(V)는 전체 시간 복잡도에 큰 영향을 미치지 않으므로 삭제 
• E > V 이므로 (최대 V2=E 가 될 수 있음), O((V+E)logV)는 간단하게 O(ElogV) 로 나타낼 수 있다. 

 

- 개선된 프림 알고리즘은 O(E log V)만큼의 시간복잡도를 갖는다.