07. greedy algorithm, prim algorithm [2 2주차]

7. Greedy Algorithm, Prim Algorithm [2-2주차]

2024년 1월 9일 화요일

오후 11:09

<Greedy Algorithm 개요>

답을 찾기 위해 선택을 반복하는 알고리즘들 중 비교적 간단한(?) 방법으로 선택하고, 선택한 후 바꾸지 않는 알고리즘

 

ex) selection sort

선택 정렬도 직관적인 그리디 알고리즘. 뒤에서 가장 작은 것을 골라 앞쪽으로 보냄. 앞쪽은 이미 선택된 것들. 앞쪽의 원소들을 바뀌지 않음.

 

 

<Minimun Spanning Tree>

위와 같은 multi weight(가중치) graph가 있다.

위 그래프는 연결 그래프이다.

• 연결 그래프 : 모든 정점의 쌍이 경로로 연결된 그래프

 

모든 정점을 트리 형태로(사이클이 없도록) 연결하는 간선들의 집합을 가중치가 최소가 되도록 찾아내어라.

-> 최소 신장 트리 문제

 

사이클이 안 되도록 하는 이유 : 사이클에서 간선 하나를 끊어도 사이클의 모든 정점이 연결된 상태는 유지된다. 따라서 사이클이 형성되면 불필요하게 가중치 합이 늘어나게 된다.

 

5개의 정점을 가중치가 최소가 되도록 연결하려면, 4개의 간선이 필요하다.

 

 

<Prim Algorithm>

최소 신장 트리를 찾아내는 알고리즘

 

1.     하나의 노드를 가진 트리로 시작(그래프의 아무 노드나 선택한다는 뜻)

2.     트리에 인접한 간선들 중 가장 작은 가중치를 가진 간선을 추가

a.     단, 사이클을 만들지 않아야 함

3.     Spanning Tree가 될 때 까지 반복

 

 

<Prim Algorithm의 증명>

증명 과정 주의사항 : 정답이 여러 개일 수 있음.

 

간선들의 집합 T_mst가 임의의 정답이라고 하자.

Prim이 만들어 가는 답 T가 T⊆T_mst를 유지한다는 것을 증명해 보자.

 

base : T의 원소 개수 |T| = 0 일 때, T⊆T_mst 이다.

step : T_mst가 될 수 있는 하나의 특수한 정답을 T_mst0라 하자.

|T| = k일 때 T⊆T_mst0 라 한다. Prim 알고리즘이 한번의 선택을 진행하여 T' = T∩{(u, v)}를 만든다.

• case1) T'⊆T_mst0이면 T'⊆T_mst 를 만족한다.
• case2) T'이 T_mst0의 부분집합이 아니라고 하자. 즉, 간선 (u, v)는 T_mst0에 없다. "T_mst0에서 u로부터 v로의 경로 p"에 (u, v)를 추가하면 사이클이 된다.

 

이때, T가 이루는 트리의 노드에 붙어 있으면서, T에 포함되지는 않는 간선 (x, y)가 경로 p에 적어도 하나 존재한다. Prim 알고리즘의 2.a 에 따르면, u는 트리T에 포함되고, v는 포함되지 않기 때문이다 (또는 v만 포함되고 u는 포함되지 않음).

트리의 성질에 따르면, u에서 v로의 경로는 p 하나뿐이므로, (x, y)를 삭제하면 T_mst0는 두 개로 나뉜다. 여기에 (u, v)를 추가하면 나뉜 요소가 다시 연결되고, 새로운 신장 트리 T_st0가 만들어진다.

 

Prim 알고리즘을 사용해 (u, v)를 선택하였으므로

• w(u, v) <= w(x, y)

가 성립한다. 따라서

• w(T_st0) = w(T_mst0) - w(x, y) + w(u, v)
• w(T_st0) <= w(T_mst0)

T_mst0는 최소 신장 트리이므로 w(T_st0) = w(T_mst0).

T_st0도 최소 신장 트리이다.

T'⊆T_st0 이므로, |T| = k+1일 때 T⊆T_mst가 성립한다.

 

따라서 Prim 알고리즘은 T⊆T_mst를 유지하고, 최소 신장 트리를 찾아내게 된다.

 

 

<Prim Algorithm의 구현과 성능>

Algorithm Prim(G, T)

T <- Empty Set  // 트리에 들어간 간선들의 집합

U <- {1}  // 트리에 들어간 노드들의 집합

while U!=V do

U의 한 노드와 V-U의 한 노드를 잇는 간선들 중 가중치가 가장 작은 것 (u, v)를 찾는다

(u, v)를 T에 추가

v 를 U에 추가

 

• 성능 분석

노드가 V개, 간선이 E개일 때

while 문은 V-1번 반복된다.

 

가중치가 가장 작은 간선 찾기 : Priority Queue 이용

힙에 원소를 추가하고 제거하는 연산은 O(logn)시간이 걸린다. (n은 힙에 있는 원소의 개수)

모든 간선이 각각 2번씩 priority queue에 들어간다.

따라서 힙의 원소 개수는 최대 2E 이며, 최대 2E개의 원소가 힙에 들어갔다 나오게 된다.

-> priority queue를 통한 간선 선택은 총 O(E logE) 시간이 걸린다.

 

간선과 노드를 집합에 추가하는 연산은 O(1) 시간이 걸린다.

 

시간복잡도는

O(E logE) + (V-1) * O(1) = O(E logE + V)

 

V-1 <= E <= _VC₂ = kV² , log(V-1) <= logE <= 2logV + logk

이므로

O(E logE + V) = O(E logE) = O(E logV)

이다.