프림 알고리즘의 최적 여부 검증 Optimality Proof 프림 알고리즘은 매 결정을 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택하는 그리디 알고리즘에 기반한다. 그 순간의 선택은 그 당시에는 최적일 수도 있지만 순간순간 최적이라고 생각했던 해답을 모아서 최종적인 해답을 만들었을 때, 그 해답이 궁금적으로 최적이라는 보장이 없다. 따라서 그리디 알고리즘은 항상 최적의 해답인지 검증할 필요가 있다. 프림 알고리즘이 찾아낸 신장트리가 최소비용인지 검증해야 한다. 다시 말해서, 프림 알고리즘이 최적인지를 보여야 한다. 비방향성 그래프인 G = (V, E)가 주어진다. G는 가중치가 있는 그래프이고, 이것은 전체 정점의 집합V와 전체 간선의 집합E로 이루어져 있다. F는 방문한 간선이고 E..
