Prim's Algorithm(프림 알고리즘)

0. 시작에 앞서...

- Minimum-Spanning-Tree 문제는 그래프의 최적화 문제 중 유명한 하나의 문제이다.

- 모든 정점을 최소비용으로 연결할 수 있는 트리를 구하거나 그 비용을 알아내는 문제.

- 즉 최적해(optimal solution)을 찾아내는 문제.

- 최소신장트리를 구하는 유명한 알고리즘으로 Prim과 Kruscal이 있는데 이번 시간에는 prim의 알고리즘을 다룬다.

 

 

1. 최소신장트리

- 최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것

- 최소신장트리는 무향연결그래프에서 정의되며, 즉 connected, undirected,weight graph.

- 그래프의 weight는 그래프를 이루고 있는 subgraph들의 간선 가중치의 합.

- 트리 이므로 당연히 사이클이 발생해서는 안된다.

 

 

2.프림알고리즘의 아이디어

- 프림알고리즘은 트리를 점점 키워나가는 알고리즘이다.

- 먼저, 임의의 starting vertex를 선택한다.( 보통 그것이 root가 된다.)

- 연결된 간선 중 가중치가 작은 정점들을 차례대로 붙여나간다.

- 정점(vertices)들은 3종류의 disjoint categories로 나누어지는데

  1. Tree vertices

  2. Fringe vertices

  3. Unseen vertices

- 맨 처음에 모든 정점들은 unseen vertices이고 fringe set을 거쳐서 tree set으로 들어가게 된다.

  (단, 처음 선택하는 root vertex만이 fringe set을 거치지 않고  tree set에 들어가게 된다.)

- 예시로 한번 살펴보자(Example)

(1) 그래프는 아래와 같고 A라는 점을 root로 선택해서 시작한다고 가정.

(2) root를 제외한 모든 정점들은 unseen으로 setting

A에서 인접한 정점들을 fringe set에 넣어준다.

(3) (2)에서 가장 가중치가 적은 B를 선택해서 tree set에 넣고 다시 트리 정점으로 부터 인접한

     정점들을 fringe set에 넣는다. B와 인접해있는 C가 추가되었고..

     간선이 중복되는 경우가 있는데 이 경우 선택이 필요하다.

     AG(3) VS BG(6) 인데 AG가 가중치가 더 적으므로 AG를 선택한다.

(4) 이와 같은 과정을 모든 정점을 포함할 때 까지 하는 것이다.

     각 과정에서 가장 가중치가 적은 간선에 연결된 정점을 선택한다는 점에서 그리디 라고도 할 수 있겠다.

     FRINGE SET 은 Min Priority Queue를 이용하면 편하다.

 

 

3. Prim's Algorithm

 

4. 분석 (Analysis)

- 어떤 구조로 fringe set을 구현하느냐에 따라 차이가 있다.

- 일단, 모든 정점이 fringeset을 거쳐 tree set에 하나씩 들어가므로 (정점의 개수를 n이라 하면)

- unsorted array로 구현시 O(n^2)이라고 할 수 있다. 

- 힙으로 구현하면 fringe set에 삽입하는 시간을 O(log n)으로 줄일 수 있다.

- 프림 알고리즘의 경우 정점 개수에 dependent하므로 

- 그래프가 dense(간선이 많을 경우) 할 경우 프림의 알고리즘이 유리하다.