Prim's Algorithm

Graph

먼저 prim's algorithm을 들어가기전에 graph란 무엇인지에 대해 정의하고 시작하겠습니다.

Graph란 vertex와 edge 그리고 각 edge에 해당하는 weight로 구성되어있는 문제 구조를 의미합니다.

이러한 graph는 여러 기준을 통해 구분이 가능한데 해당 구분에 따라 적용되는 알고리즘과 방법이 달라질 수 있으므로 명확하게 이해하고 넘어가야합니다.

지금 부터 다룰 graph들은 임의의 특정 두 vertex에 대하여 이 둘을 잇는 edge는 없거나 하나만 있는 경우만 생각합니다.
(방향이 있는 edge의 경우 서로 다른 edge라고 생각합니다.)

1) edge의 방향 여부

1. directed graph (digraph)
   edge에 방향이 있는 graph를 의미합니다. 즉 edge의 양 끝 vertex A, B에 대하여 A->B edge와 B->A edge는 서로 다른 edge입니다.
2. undirected graph
   edge에 방향이 없는 graph로 두 vertex A, B에 대하여 둘 사이의 edge에는 A->B, B->A가 하나의 edge에 대하여 가능합니다.

2) weight의 음수 존재 여부

1. negative weight graph
   graph의 edge들 중 weight가 음수인 값이 존재하는 graph입니다.
   이는 shortest path를 풀때 상당히 중요한 요인으로 자리잡습니다.
2. non-negative weight graph
   graph의 edge들 중 weight가 음수인 값이 존재하지 않는 graph입니다.

3) 성질

그래프는 $G=(V,E)$로 표현됩니다.
여기서 $V$는 vertex 집합, $E$는 edge 집합을 의미합니다.
이러한 그래프는 다음의 성질을 가집니다.
(1) $E\subseteq V\times V$
(2) $|E|=O(V^2)$
(3) $|E|\geq |V|-1$

4) adjacency matrix (인접행렬)

인접행렬 $A$는 다음과 같이 표현됩니다.
$A[i,j]= 1\space\space\space if(i,j)\in E\space\space\space or\space\space\space 0\space\space\space if (i,j) \notin E$
행렬$A$의 원소가 1이 많을 경우를 dense, 0이 많을 경우 sparse하다고 표현합니다..

5) adjacency list

$Adj[v]\space\space is\space\space a\space\space list\space\space the\space\space list\space\space of\space\space vertices\space\space adjacent\space\space to\space\space v\in V$
undirected graph의 경우 $|Adj[v]|=degree(v)$
digraph의 경우 $|Adj[v]|=out-degree(v)$ 로 표현 됩니다.

Handshaking Lemma : $\sum_{v\in V}degree(v)=2|E|\space\space for\space\space undirected\space\space graphs$

MST - Minimum Spanning Tree (최소 신장 트리)

• Input : connected, undirected graph $G=(V,E)$ with weight function $w : E->R$
• Output : spanning tree T of minimum weight $\space\space$ $w(T)=\sum_{(u,v)\in T}w(u,v)$

즉 그래프 G의 모든 vertex를 지나는 경로의 weight합이 최소인 tree를 의미합니다.

1) MST는 optimal substructure를 가진다.

즉 MST T에 대하여 특정 edge $(u,v)\in T$를 제거하였을 때, 둘로 나뉘는 T의 부분들을 각각 T1, T2라고 하겠습니다.
이때 다음의 정리(Theorem)이 성립합니다.
The subtree T1 is an MST of $G_1=(V_1,E_1)$, the subgraph of $G$ induced by the vertices of T1
귀류법을 이용하면 쉽게 증명되므로 증명은 pass 하겠습니다.
아이디어는 $G1$에 대해 특정 $T1^,$이 기존의 $T1$보다 더 적은 weight를 가지고 있다고 가정하면 모순됨이 쉽게 보여집니다.

이때 이러한 특징(overlapping subproblems)으로 인하여 DP의 조건이 만족되고 따라서 DP로 풀 수 있으나 보다 더 간단한 방법이 존재합니다.

바로 Greedy-Choice Property입니다!

2) Greedy-Choice Property

해당 속성은 두 가지 조건위에 성립합니다.
1. overlapping subproblem
2. a locally optimal choice is globally optimal

이때 MST도 아래와 같이 이러한 속성을 지닙니다.
Let $T$ be the MST of $G=(V,E)$, and let $A\subseteq V$. Suppose that $(u,v) \in E$ is the least-weight edge connecting $A$ to $V-A$. Then, $(u,v)\in T$.
마찮가지로 귀류법으로 $(u,v)$가 $T$에 속하지 않는다고 가정하면 쉽게 모순이 되어 증명할 수 있습다.

prim's algorithm

드디어 prim's algorithm이 등장합니다.

Q<-V
key[v] <- infinite for all v in V
key[s] <- 0 for some arbitrary s in V
while Q not empty
	u <- extract-min(Q)
    	for each v in Adj[u]
        	if v in Q and w(u,v)<key[v]
            	key[v]<-w(u,v)
                pi[v]<-u
                
                at the end, {(v,pi(v))} forms the MST.

시간 복잡도는 위의 것을 계산해보면
$Time=\theta(V)*T_{EXTRACTION}+\theta(E)*T_{DECREASE-KEY}$
여기서 $T_{EXTRACTION}$은
array : O(V), binary heap : O(logV), Fibonacci heap : O(logV)
여기서 $T_{DECREASE-KEY}$는
array : O(1), binary heap : O(logV), Fibonacci heap : O(1)
이때 Fibonacci heap은 amoritized한 방법으로 시간 복잡도를 계산한 것이다.
나머지는 asymptotic한 방법이다.

구현

(todo)