[알고리즘] 프림(Prim's) 알고리즘 파이썬, 최소신장트리(MST) 찾기, 파이썬 heapq, defaultdic

[알고리즘] 크루스칼(Kruskal) 알고리즘 파이썬, 최소신장트리(MST), union-find기법(union-by-rank, path-compr

 

# 설명

크루스칼 알고리즘과는 다른 점은, 모든 엣지를 알고있어서 정렬한 후 엣지를 선택했던 이전과는 다르게, 주어진 시작노드로부터 인접 간선을 통하여 노드를 연결하는 것이 다르다.

후보군 간선 리스트(최소힙)를 만든 후, 노드가 선택될때 마다 후보군에 추가한다. 추가한 후보군에서 가장 작은 간선을 선택하여 연결한다.

연결을 확정짓기 위해서는 해당 엣지를 통해 연결되는 노드가 이미 선택됐는지를 판단한다. 선택된 노드였다면 건너뛴다. 그렇게 노드가 선택되면 다시 후보군에 넣어주고의 과정을 반복한다.

 

## defaultdic

dic에 없는 '키'값에 접근하면 오류가 나는데, defaultdic을 사용하면, 존재하지 않았더라면 인자로 넘겨준 데이터타입으로 value를 만들어준다.

 

# 사용된 그래프

# 코드

"""
  Prim알고리즘을 이용하여 MST(최소신장트리)구하기
  크루스칼 알고리즘은 모든 엣지의 정보를 이미 알고 있는 상태에서 출발하지만,
  프림알고리즘은 주어진 시작노드에서부터 하나씩 추가해나가면서 구현함
"""
from collections import defaultdict
import heapq

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

def prim(start_node,edges):
  mst = list()
  adjacent_edges = defaultdict(list)
  selected_vertex = set()

  # 노드별 엣지 초기화 해주기 ( u->v )
  for weight,node_u,node_v in edges:
    adjacent_edges[node_u].append((weight,node_u,node_v))
    adjacent_edges[node_v].append((weight,node_v,node_u))

  # 시작 노드 넣어주기
  selected_vertex.add(start_node)
  candidate_edges = adjacent_edges[start_node]
  heapq.heapify(candidate_edges)

  # 검사 및 선택
  while candidate_edges:
    cur_weight,cur_u,cur_v = heapq.heappop(candidate_edges)
    if cur_v not in selected_vertex:
      selected_vertex.add(cur_v)
      mst.append((cur_weight,cur_u,cur_v))

      for edge in adjacent_edges[cur_v]:
        if edge[2] not in selected_vertex:
          heapq.heappush(candidate_edges,edge)

  return mst

if __name__ == '__main__':
    my_edges = make_edges()
    answer = prim('A',my_edges)
    print(answer)

 

# 시간복잡도

최소 힙구조를 사용

O(E log E)