[Algorithm & DS] 그래프 - Prim 알고리즘

✅ Prim 알고리즘

✏️ 프림 알고리즘이란

• 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 가중치 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택해가며 최소 신장 트리를 확장해가는 방식

✏️ 프림 알고리즘의 동작 방식

1. 임의의 정점을 선택하여 '연결된 노드 집합'에 삽입
2. 선택된 정점에 연결된 간선들을 간선 리스트에 삽입
3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서,
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면 스킵 (cycle 발생을 막기 위함)
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리'에 삽입
4. 추출한 간선은 간선 리스트에서 제거
5. 간선 리스트에 더이상 간선이 없을 때까지 3-4번을 반복

✏️ 프림 알고리즘 구현

from collections import defaultdict
from heapq import *

def prim(first_node, edges) :
    mst = []

    # 모든 간선의 정보를 adjacent_egdes에 저장
    adjacent_edges = defaultdict(list)
    for weight, node1, node2 in edges :
        adjacent_edges[node1].append((weight, node1, node2))
        adjacent_edges[node2].append((weight, node2, node1))

    # 처음 선택한 노드를 연결된 노드 집합에 삽입
    connected_nodes = set(first_node)
    # 선택된 노드에 연결된 간선을 간선 리스트에 삽입
    candidated_edge = adjacent_edges[first_node]
    # heap 구조로 바꾸며, 가중치 기준 오름차순으로 정렬
    heapify(candidated_edge)

    while candidated_edge :
        weight, node1, node2 = heappop(candidated_edge)
        # 사이클 있는지 확인 후 연결
        if node2 not in connected_nodes :
            connected_nodes.add(node2)
            mst.append((weight, node1, node2))

            for edge in adjacent_edges[node2] :
                if edge[2] not in connected_nodes :
                    heappush(candidated_edge, edge)

    return mst

edges = [
    (7, 'A', 'B'), (5, 'A', 'D'),
    (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'),
    (5, 'C', 'E'),
    (15, 'D', 'E'), (6, 'D', 'F'),
    (8, 'E', 'F'), (9, 'E', 'G'),
    (11, 'F', 'G')
]

prim('A', edges)

# 결과 출력
# [(5, 'A', 'D'),
#  (6, 'D', 'F'),
#  (7, 'A', 'B'),
#  (7, 'B', 'E'),
#  (5, 'E', 'C'),
#  (9, 'E', 'G')]

🤓 프림 알고리즘의 시간 복잡도

• 최악의 경우 while문에서 모든 간선에 대하여 반복
  • 최소 힙 구조 사용 -> O(ElogE)

✏️ 개선된 프림 알고리즘

• 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식
  • 초기화
    [노드:key] 구조를 만들어 놓고, 특정 노드의 key값은 0, 이외의 노드들의 key값은 무한대로 설정.
    모든 [노드:key] 값은 우선순위 큐에 넣음
  • 가장 key값이 적은 [노드:key]를 추출한 후(pop하므로 해당 [노드:key] 정보는 우선순위 큐에서 삭제됨)(extract min 로직이라 함)
  • 해당 노드의 인접한 노드들에 대해 key값과 연결된 가중치 값을 비교하여 key값이 작으면 해당 [노드:key]값을 갱신
    • [노드:key] 값 갱신시, 우선순위 큐는 최소 key 값을 가지는 [노드:key]를 루트노드로 올려놓도록 재구성함 (decrease key 로직이라고 부름)
• 개선된 프림 알고리즘 구현시 고려사항
  • 우선순위 큐(최소힙) 구조에서, 이미 들어가 있는 데이터의 값 변경시, 최소 값을 가지는 데이터를 루트노드로 올려놓도록 재구성하는 기능이 필요함
  • 구현 복잡도를 줄이기 위해, heapdict 라이브러리를 통해 해당 기능을 간단히 구현

"""
    heapdict을 쓰는 이유:
    새롭게 heap에 push하거나 pop하지 않아도
    기존의 heap 내용만 update한다 하더라도
    알아서 최소 힙의 구조로 업데이트 함
    * heapdict을 쓰기 전에 HeapDict 라이브러리 설치하기:
      -> pip install HeapDict
"""

from heapdict import heapdict

def prim(graph, start) :
    mst, keys, previous, total_weight = [], heapdict(), dict(), 0

    for node in graph.keys() :
        keys[node] = float('inf')
        previous[node] = None
    keys[start], previous[start] = 0, start

    while keys :
        current_node, current_key = keys.popitem()
        mst.append([previous[current_node], current_node, current_key])

        total_weight += current_key
        for adjacent, weight in graph[current_node].items() :
            if adjacent in keys and weight < keys[adjacent] :
                keys[adjacent] = weight
                previous[adjacent] = current_node

    return mst, total_weight


graph = {
    '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': 15, 'F': 6},
    'E': {'B': 7, 'C': 5, 'F': 8, 'G': 9},
    'F': {'D': 6, 'E': 8, 'G': 11},
    'G': {'E': 9, 'F': 11}
}

mst, total_weight = prim(graph, 'A')
print(mst)
print(total_weight)

# 결과 출력
# [['A', 'A', 0], ['A', 'D', 5], ['D', 'F', 6], ['A', 'B', 7], ['B', 'E', 7], ['E', 'C', 5], ['E', 'G', 9]]
# 39

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

• 최초 key 생성 시간 복잡도 : O(V)
• while 구문과 keys.popitem() 의 시간 복잡도 : O(VlogV)
  • while 구문은 V(노드개수)번 실행됨
  • heap에서 최소 key값을 가지는 노드 정보 추출시(pop)의 시간 복잡도 : O(logV)
• for문 의 총 시간 복잡도 : O(ElogV)
  • for문은 while문 반복시에 결과적으로 총 최대 간선의 수 E만큼 실행 가능 O(E)
  • for문 안에서 key값 변경시마다 heap 구조를 변경해야하며, heap에는 최대 V개의 정보가 있으므로 O(logV)
• 따라서, 총 시간 복잡도는 O(V + VlogV + ElogV)
  • O(V)는 전체 시간 복잡도에 큰 영향을 미치지 않으므로 삭제,
  • E > V 이므로 최대 (V^2 = E 가 될 수 있음), O((V+E)logV)는 간단하게 O(ElogV) 로 나타낼 수 있음

🤓 Kruskal 알고리즘과 Prim 알고리즘 비교

• 둘다 탐욕 알고리즘이다. (당장 눈앞의 최소 비용을 선택. 결과적으로 최적의 솔루션을 찾음.)

• 크루스칼 알고리즘은 가장 가중치가 작은 간선부터 선택하면서 최소 신장 트리를 구함

• 프림 알고리즘은 특정 정점에서 시작하여, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택(간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중치가 작은 간선을 선택)하는 방식으로 최소 신장 트리를 구함

• 시간 복잡도 비교

  • Kruskal 알고리즘의 시간 복잡도 : O(N^2)

  • Prim 알고리즘의 시간 복잡도 : O(ElogE)
    (( 어떤 자료구조를 사용하느냐에 따라 시간 복잡도는 달라질 수 있고 개선될 수 있음 ))

  • 정점에 비해 간선이 적은 희소 그래프에서는 Kruskal 알고리즘이 적합

  • 정점에 비해 간선이 많은 밀집 그래프에서는 Prim 알고리즘이 적합