프림알고리즘2 프림 알고리즘 증명 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. 프림 알고리즘 Prim's Algorithm 일정 시간 복잡도 MST(minimum spanning tree)구하는 알고리즘 정점 선택 기반으로 가중치 제일 낮은 방향으로 이전 단계의 신장트리를 확장해나간다. 트리가 N-1개의 간선을 가질 때까지 반복한다. 의사 코드를 보면 다음과 같다. void prim(int n, const numberW[][], set_of_edges& F) //정점 개수, 간선 정보, 방문 간선 { index i, vnear; number min; edge e; index nearest[2..n]; //해당 인덱스의 정점에서 가장 가까운 정점 정보 number distance[2..n]; //현재 방문한 정점에서 해당 인덱스의 정점까지 거리(최단) F = ∅; for(i = 2; i 2021. 6. 8. 이전 1 다음