프림 알고리즘(Prim Algorithm)

프림 알고리즘(Prim Algorithm)

프림 알고리즘(Prim Algorithm)

프림 알고리즘 : 크루스칼과 같이 MST(최소 신장 트리)를 찾는 알고리즘

시간 복잡도 : 변의 개수를 E, 꼭지점의 개수를 V라고 할 때, 이진 힙을 사용하면 O(ElogV)

프림 알고리즘 개요:

- 하나의 정점에서 연결된 간선들 중 하나씩 선택하면서 MST를 만들어 가능 방식

- 크루스칼 알고리즘과 같이 그리디 기법(탐욕 기법)에 기반

(1) 임의의 정점 하나를 선택해서 시작

(2) 선택한 정점과 인접한 정점들 중 최소 비용의 간선이 존재하는 정점을 선택 (트리 안 에 속한 정점은 제외)

(3) 모든 정점이 선택될 때 까지 위를 반복

Node 1 2 3 4 5 6 7 Visited T F F F F F F

처음 시작할 노드를 1로 잡았다. 따라서 방문 체크를 하는 배열에서 1은 True로 갱신된다.

Node 4 2 Cost 5 7

1번 Node와 인접한 2번 Node와 4번 Node가 우선순위 큐(이진 힙)에 들어간다.

Node 1 2 3 4 5 6 7 Visited T F F T F F F

큐에 가장 앞에 있는 4번 노드가 선택되고 방문 배열의 4번 노드가 True로 갱신된다.

Node 6 2 2 5 Cost 6 7 9 15

큐에 4번 노드와 인접한 노드들이 들어간다.

Node 1 2 3 4 5 6 7 Visited T F F T F T F

큐에 가장 앞에 있는 6번 노드가 선택되고 방문 배열의 6번 노드가 True로 갱신된다.

Node 2 5 2 7 5 Cost 7 8 9 11 16

6번 노드와 인접한 노드들이 큐에 들어간다.

Node 1 2 3 4 5 6 7 Visited T T F T F T F

큐에 가장 앞에 있는 2번 노드가 선택 되고 방문 배열의 2번 노드가 True로 갱신된다.

Node 5 3 5 7 5 Cost 7 8 8 11 15

2번 노드와 인접한 노드들이 큐에 들어간다. 이 때, 2번 노드와 4번 노드가 모두 True 이므로 2->4 간선은 큐에 삽입되지 않는다.

Node 1 2 3 4 5 6 7 Visited T T F T T T F

큐에 가장 앞에 있는 5번 노드가 선택 되고 방문 배열의 5번 노드가 True로 갱신된다.

Node 3 3 7 7 Cost 5 8 9 11

5번 노드와 인접한 노드들이 큐에 들어간다. 이 때도 위와 마찬가지로 방문한 노드로 향하는 간선은 제외한다.

Node 1 2 3 4 5 6 7 Visited T T T T T T F

큐에 가장 앞에 있는 3번 노드가 선택 되고 방문 배열의 3번 노드가 True로 갱신된다.

Node 7 7 Cost 9 11

3번 노드와 인접한 노드들은 모두 방문했으므로 큐에는 방문한 노드를 제외한 7번 노드 가는 간선들만 들어간다.

Node 1 2 3 4 5 6 7 Visited T T T T T T T

큐에 가장 앞에 있는 7번 노드가 선택 되고 방문 배열의 7번 노드가 True로 갱신된다.

모든 노드를 방문했으므로 MST가 완성되었다. 완성된 MST는 아래와 같다.

크루스칼 알고리즘과 마찬가지로 MST를 구하는 알고리즘이다. 완성된 모습도 같은 것을 확인할 수 있다.

크루스칼 vs 프림

- 프림은 정점 중심 알고리즘이고 크루스칼은 간선 중심의 알고리즘이다.

- 프림은 인접한 정점을 선택하며 트리를 구성하는 반면 크루스칼은 최소 비용의 간선을 대입하면서 트리를 구성한다.

- 프림은 트리를 구성하는 중 싸이클이 발생하지 않지만 크루스칼은 싸이클이 발생할 가능성이 있으므로 싸이클이 발생하는지 검사하며 진행한다.

- 프림의 경우 자료 구조의 따라 성능이 바뀐다.

- 간선의 개수가 작은 경우 크루스칼, 간선의 개수가 많은 경우 프림을 사용한다.

다음 포스트에서는 프림 알고리즘의 구현과 예제를 다뤄보겠습니다.

from http://dabonee.tistory.com/41 by ccl(A) rewrite - 2021-09-26 00:00:44