ImJay

최소 비용 신장 트리 알고리즘 작동원리 이해하기 ( Prim / Kruskal ) 서론 [파이썬/Python] 최소 비용 신장 트리 알고리즘 구현하기 ( Prim / Kruskal ) 최소 비용 신장 트리 알고리즘 구현하기 서론 신장 트리(Spanning tree)란 연결된 비방향성 그래프에서, 노드는 그대로 유지한 채로, 순환경로(cycle)가 없어지도록 이음선을 제거하여 구성한 연결된 develop247.tistory.com 이전 시간 구현하였던 Prim, Kruskal 알고리즘의 작동원리에 대해 간단한 예제를 통해 그림으로 이해해보려고 합니다. 본론 문제 1. Prim 알고리즘을 이용하여 위 그래프의 최소비용 신장 트리를 구하는 과정을 제시하시오. 처음 start_node = 1이므로, d[1] =..

최소 비용 신장 트리 알고리즘 구현하기 서론 신장 트리(Spanning tree)란 연결된 비방향성 그래프에서, 노드는 그대로 유지한 채로, 순환경로(cycle)가 없어지도록 이음선을 제거하여 구성한 연결된 부분그래프입니다. 최소 신장 트리(Minimum spanning tree, MST)는 주어진 그래프의 부분 그래프인 여러 신장 트리 중에서 모든 간선의 가중치 합이 최소가 되는 신장트리입니다. 신장 트리의 의미와 최소 신장 트리를 구하는 두 가지 알고리즘인 프림 알고리즘(Prim algorithm)과 크루스칼 알고리즘(Kruskal algorithm)에 대해 코드를 통해 이해해보도록 하겠습니다. 본론 minimum_spanning_tree.py import sys class Graph: def __i..