안녕

앞서 보았듯이 시간 복잡도는 다음과 같습니다. Prim's Algorithm : \(T(n)\,\epsilon\,\theta(n^2)\) Kruskal's Algorithm : \(W(m, n)\,\epsilon\,\theta(mlgm) \, or \, \theta(n^2lgn)\) 또한 \(n-1 \leq m \leq \frac{n(n-1)}{2}\)이 성립합니다. 따라서 프림 알고리즘과 크루스칼의 알고리즘은 다음과 같은 상황에서 비교할 수 있습니다. For a Sparse Graph edge의 개수인 m이 n-1과 가까운 희소 행렬의 경우에는 Kruskal's Algorithm is \(\theta(nlgn)\)이므로, Prim's Algorithm 보다 빠릅니다. For a Dense Graph e..

문제)

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가 최소가 되는 S..