1. 프림 알고리즘 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘 임의의 정점을 하나 선택해서 시작 선택한 정점들과 인접한 정점들 중 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때 까지 (2) 반복 두 종류의 상호 배타 집합(disjoint set)이 필요 트리 정점 : 최소 신장 트리에 선택된 정점들 비트리 정점 : 선택되지 않은 정점들 소스코드 # G : 그래프 # s : 시작 정점 def mst_prim(G, s): key = [INF] * N # 가중치를 무한대로 초기화 pi = [None] * N # 트리에서 연결될 부모 정점 초기화 visited = [False] * N # 방문 여부 초기화 key[s] = 0 # 시작 정점의 가중치를 0으로 ..
