본문 바로가기

Prim의 알고리즘1

15-4. 최소비용신장트리( Minimum Spanning Tree) Prim의 알고리즘 - 임의의 노드를 출발노드로 선택 - 출발 노드를 포함하는 트리를 점점 키워 감 (크러스칼은 에지들의 가중치가 작은 순서대로 접근하는 방법이었다면, 프림은 출발노드부터 연결 연결된 노드들을 탐색하여 트리를 키운다) - 매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택 위의 그래프에서 출발 노드가 초록색 노드라고 하면, 출발 노드에 인접한 노드들을 A라 하면, 그 부분트리에 포함된 노드들의 집합은 V of A(빨간 노드들)라 하자. (a) : 출발노드 a 에서 인접한 노드 b와 노드 k 가 있다. 가중치가 작은 에지는 4이므로 노드 b를 선택한다. (b) : 이제 노드 a 와 노드 b는 V of A의 부분집합이 되었다. (c.. 2020. 12. 17.

이전 1 다음

티스토리툴바