minimum spanning trees
-
[Python] 최소신장트리(Minimum Spanning Trees, MST) 구현하기 by Prim프로그래밍/알고리즘 2022. 9. 21. 10:57
이번 글에서는 파이썬 언어를 사용하여 Prim방식 기반 최소신장트리를 구현한다. 1. 문제 가중치가 있는 무방향성 그래프가 주어졌을 때, 최소 신장 트리(MST, Minimum Spanning Tree)의 가중치의 합을 구하라 2. 파이썬 구현 기본적으로 주어지는 정보 import heapq node_n, edge_n = 4,6 graph_info = [(0,1,6),(0,2,7),(2,3,2),(1,2,5),(1,3,3),(0,3,9)] start_node = 0 # 탐색을 시작할 노드 주어진 그래프로부터 인접 딕셔너리 생성(인접 리스트로 해도 상관없음) 무방향 그래프이기때문에 node_a,node_b의 간선정보를 서로 넣어준다 # 인접 딕셔너리 생성 adj_dic=dict([(n,[])for n in..