최소신장트리 (MST) 그래프에서의 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 신장 트리 n 개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소신장 트리 (Minimum Spanning Tree) 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 MST 표현 그래프 간선들의 배열 인접 리스트 부모 자식관계와 가중치에 대한 배열 (트리) Prim 알고리즘 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식 임의 정점을 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택..
