안녕

앞서 보았듯이 시간 복잡도는 다음과 같습니다. 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..

문제)

최소 비용 신장 트리를 풀기 위한 또 다른 알고리즘은 크루스칼 알고리즘입니다. 크루스칼 알고리즘은 각 vertex마다 본인만 포함하는 서로소 집합 (disjoint set)을 만드는 것부터 시작합니다. 이후, 가중치가 작은 것부터 차례대로 edge를 검사합니다. 만약 edge가 서로소 부분 집합들에 있는 두 개의 vertex를 연결한다면 edge를 추가하고, 두 개의 부분 집합을 하나의 집합으로 합칩니다. 이 반복은 모든 disjoint set이 하나의 set이 될 때까지 반복합니다. 슈도 코드로 작성하면 다음과 같습니다. F = 0 create disjoint set of V sort the edges in E in nondecreasing order while the instance is not so..