프림알고리즘증명1 프림 알고리즘 증명 Prim's Algorithm Proof 그리디 알고리즘은 매 순간 최적의 결과만 추구하기 때문에 최종적으로 얻게 되는 결과가 최적의 결과인지는 알 수 없다. 그렇기 때문에 그리디 알고리즘은 최적의 결과인지 판단하는 것이 필요하다. 프림 알고리즘 역시 그리디 알고리즘에 속한다. 그러므로 프림 알고리즘을 통해서 얻는 결과가 최적 결과인지 확신할 수 없다. 그런데 프림 알고리즘 결과는 항상 최적의 결과라고한다. 이를 증명하는 법을 알아보자. G는 가중치가 있고 방향성이 없는 그래프이다. 이는 전체 정점 V와 전체 간선 E로 이루어져있다. F는 방문한 간선이다. F는 E에 속한다. Y는 V에 속하면서 간선 F를 통해 방문 했던 정점들이다. 그래서 G = (V,E) 이고 F ⊆ E, Y ⊆ V, F는 promising하다고 해보자. 이 때 promis.. 2021. 6. 8. 이전 1 다음