신장트리 썸네일형 리스트형 Prim 알고리즘 발표자료 및 소스코드(matlab) Prim 알고리즘의 정의 최소비용 신장트리(MST) -주어진 그래프의 신장트리 중 전체 가중치의 합이 최소가 되는 것 우선순위 우선탐색(PFS)방식 -가설비용에 해당하는 간선에 가중치를 두고 가중치가 작은 것일수록 우선순위가 높다고 정의한 것 1. 시작할 정점을 임의로 선택한다. 2. 선택된 정점들에 부속된 간선들 중 가중치가 제일 작은 간선을 선택하여 최소 비용 신장 트리에 포함시킨다. 3. 선택된 간선에 인접한 정점들에 부속된 간선들에 대해서도 2를 반복한다. 4. 만약 사이클이 발생하면 선택한 간선은 제거하고 그 다음 가중치가 작은 간선이 있으면 선택하고 없으면 그 전에 방문한 정점에 연결된 간선에 대해 2를 반복한다. 5. 모든 정점이 연결되면 종료한다. % Program 'prim_1.m' (v.. 이전 1 다음