1. 그래프 최소 비용 문제 : 최소 신장 트리 문제 vs 최단 경로 문제 최소 신장 트리 문제 가중치 그래프에서 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제 최단 경로 문제 시작 정점에서 목표 정점까지 가는 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제 2. 신장 트리(Spanning Tree) 정점인 n개인 undirected graph에서 n개의 정점과 n-1개의 간선으로 구성된 트리 즉, 모든 vertex set을 포함해야한다. 신장 트리의 수는 정점의 개수와 간선의 수의 비례한다. 3. 최소 신장 트리(Minimum Spanning Tree) 가중치 그래프의 신장 트리 중 간선들의 가중치의 합이 최소인 신장 트리 프림 알고리즘과 크루스칼 알고리즘이 존재한다.