Comparing MST-Prim's Algorithm with MST-Kruskal's Algorithm(최소신장트리-프림 알고리즘 vs. 크러스컬 알고리즘)

Time Complexity Comparison

---

The number of edges in a connected graph is

 

$$ n-1 \leq m \leq \frac{n(n-1)}{2} \approx n^2 $$

 

👉 어떤 그래프의 정점의 개수를 n이라고 할 때, 이음선 개수(m)의 범위는 n - 1개에서 부터 n(n - 1)/2이다. 여기서 n(n-1)/2은 1부터 n-1까지의 합이다.

 

For a graph whose number of edges m is near the low end of these limits (the graph is very sparse), Kruskal’s algorithm is $\Theta(nlgn)$ which means that Kruskal's algorithm should be faster. However, for a graph whose number of edges is near the high end (the graph is highly connected), Kruskal’s algorithm is $\Theta(n^2lgn)$, which means that Prim's algorithm should be faster.

Algorithm Technique	Time Complexity (시간복잡도)	Sparse Graph (희소 그래프)	Dense Graph (밀집 그래프)
Prim's Algorithm	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$
Kruskal's Algorithm	$\Theta(mlgm)$ and $\Theta(n^2lgn)$	$\Theta(mlgm)$	$\Theta(n^2lgn)$

 

👉 이음선의 개수가 하한선 근처(n - 1에 근접)인 경우 희소 그래프(sparse graph)이고, 상한선 근처(n(n - 1)/2에 근접)인 경우는 밀집 그래프(dense graph) 이다. 

위의 성능 비교표에서 알 수 있듯이, 희소 그래프의 경우 Kruskal 알고리즘의 성능이, 밀집 그래프의 경우엔 Prim 알고리즘의 성능이 효율적임을 알 수 있다.