[알고리즘] 탐욕법 - 프림 알고리즘 (Greedy Approach - Prim's Algorithm)

Prin's Algorithm은 Minimum Spanning Tree를 찾는 가장 기초적인 알고리즘입니다.

---

1. Minimum Spanning Tree란?

 

 

우선, Minimum Spanning Tree를 알아보겠습니다.

G(graph)에 대한 Spanning Tree는 G의 모든 vertex를 포함하고, 트리인 connected 된 그래프입니다.

만약 G = (V, E)로 이루어져 있다면,  Spanning Tree인 T = (V, F)가 되어야 합니다.

이때 F는 V-1과 같습니다. 만약 F가 V-1보다 크다면 cycle이 생겨서 Tree가 되지 않습니다.

아무튼 우리가 찾아야 하는 (V, F)는 Edge의 weight의 합이 최소가 되는 집합을 찾아야 합니다.

 

edge의 weight가 최소가 되는 Spanning Tree를 우리는 Minimum Spanning Tree라고 부릅니다.

 

간단히 슈도 코드로 작성해보겠습니다.

F = 0

while the instance is not solved:
	select an edge according to some locally optimal consideration
    if adding the edge to F does not create a cycle:
    	add it
    if T = (V, F) is a spanning tree:
    	the instance is solved

간단하죠?

 

• Selection Procedure : locally optimal 한 간선을 찾는다.
• Feasibility Check : 해당 간선이 cycle을 만드는지 확인한다. 아니라면 간선의 집합에 추가한다.
• Solution Check : 간선의 집합이 spanning tree를 만족한다면 끝낸다. 아니라면 처음부터 반복한다.

 

이 문제에 대해서 locally optimal 한 간선의 성질이 하나만 존재하는 것은 아닙니다.

이 문제를 해결하는 두 가지 대표적인 알고리즘 중에 프림 알고리즘과 크루스칼 알고리즘은 locally optimal 한 간선을 서로 다른 특징을 이용해서 알아냅니다.

 

이때 탐욕법이 항상 최적의 해를 준다는 보장이 없다는 것을 항상 기억해야 합니다.

하지만 프림 알고리즘과 크루스칼 알고리즘은 둘 다 minimum spanning tree를 만든다는 사실을 증명했습니다.

 

본격적으로 Prim's Algorithm에 대해 알아보겠습니다.

---

2. Prim's Algorithm

 

그래프는 G = (V, E)입니다.

 

프림 알고리즘은 공집합인 F와 임의의 vertex를 포함하도록 초기화된 Y로 시작합니다.

이때, Y와 가까운 vertex는 V-Y 중에서, 가장 가중치가 작은 vertex입니다.

그러면 해당 vertex를 Y에 넣고, 연결된 간선을 F에 넣습니다.

이 과정은 Y = V가 될 때까지 반복합니다.

 

슈도 코드로 작성하면 다음과 같습니다.

F = 0
Y = [v_1]

while the instance is not solved:
	select a vertex in V-Y that is nearest to Y
    add the vertex to Y
    add the edge to F
    if V = Y:
    	the instance is solved

이때 selection procedure과 feasibility check는 동시에 이루어집니다.

 

만약 동일한 weight를 가진 edge가 두 개 이상 있다면 랜덤으로 선택합니다.

 

우리는 weighted graph를 adjacency matrix, W[i][j]로 정의합니다.

 

 

• W[i][j]
  • weight on edge : if there is an edge between v_i and v_j
  • infinity : if there is no edge between v_i and v_j
  • 0 : if i = j

또한 추가적으로 i = 2부터 n까지에 대하여 다음과 같이 정의되는 두 배열을 유지합니다.

• nearest[i] : index of the vertex in Y nearest to v_i
  
  • v_i에 가장 가까운 Y에 속한 마디의 인덱스
• distance[i] : weight on edge between v_i and the vertex indexed by nearest[i]
  • v_i와 nearest[i]의 간선의 가중치

 

이때 repeat 루프 안에는 두 개의 for loop가 있는데 각각 n-1회 반복합니다.

 

또한 repeat 루프를 n-1번 반복하므로 시간 복잡도는 다음과 같습니다.

 

T(n) = 2(n-1)(n-1) = \(\Theta(n^2)\)

 

 

생각보다 복잡하죠?

다음 글에는 코드를 올리겠습니다.

 

감사합니다.

 

 

 

지적 환영합니다.