프림 알고리즘

프림 알고리즘

• 프림 알고리즘은 크루스칼 알고리즘과 마찬가지로 MST를 구하는 알고리즘

동작

1. 임의의 정점을 선택해서 비어있는 T 트리에 포함시킨다.

2. T에 있는 노드와 T에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

3. 찾은 간선이 연결하는 두 노드 중, T에 없던 노드를 T에 포함시킨다.
   1. 이 때, 1에서 찾은 간선도 같이 T에 포함된다.

4. 모든 노드가 T에 포함될 때 까지, 1, 2를 반복한다.

아래는 그림으로 설명된 것입니다.

1. 임의의 정점을 선택해서 빈 T에 포함시킨다.
   1. 예를 들어 1을 선택합니다.

2. T에 있는 노드와 T에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.
   1. 빨간색과 파란색을 연결하는 간선 중 가중치가 최소인 것을 찾는다. 1-3과 1-2 중, 가중치가 더 작은 간선은 가중치가 4인 1-3을 선택한다.

3. 찾은 간선이 연결하는 두 노드 중, T에 없던 노드를 T에 포함시킨다.
   1. 노드 3을 T에 포함한다.

Uploaded by N2T