최소 비용 신장 트리를 풀기 위한 또 다른 알고리즘은 크루스칼 알고리즘입니다.
크루스칼 알고리즘은 각 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 solved:
select next edge
if the edge coneects two vertices in disjoint subsets:
merge the subsets
add the edge to F
if all the subsets are merged
the instance is solved
이때 우리는 ADT(Abstract Data Type)인 Disjoint Set이 필요합니다.
이때 서로소 집합 추상 데이터 타입은 다음의 변수와 메소드를 필요로 합니다.
- 변수
- index i
- set_pointer p, q
- 메소드
- initial(n) : initializes n disjoint subsets
- p = find(i) : makes p point to the set containing index i
- merge(p, q) : merges the two sets, to which p and q point, into the set
- equal(p, q) : returns true if p and q both point to the same set
이떄 initial 메소드는 초기에는 dset[i] = i가 되도록하면, 자기 자신만을 가지는 서로소 집합이 됩니다.
find 메소드는 while loop를 통해서 dset[i] = i면 i를 반환합니다. 이때 1 <- 2 <- 3 <- 4 <- 5 이런 식으로 연결 리스트 형태로 연결되어 있는 것보다, 2,3,4,5가 한 번에 1을 가리키게 하는 것이 많은 데이터가 입력되면 훨씬 더 효율적입니다.
merge 메소드는 p와 q의 크기를 비교해서 상대적으로 작은 집합이 큰 집합을 가리키도록 합니다.
이때도 한 번에 집합의 헤드를 가리키게 만드는게 더 효율적입니다.
마지막을 equal 메소드는 단순히 find로 찾은 집합의 헤드가 같은지를 비교하고 결과값을 리턴합니다.
프림 알고리즘에 비해 짜야하는 코드가 생각보다 깁니다.
천천히 이해하시면서 코드를 짜시면 될 것 같습니다.
시간 복잡도 분석
kruskal's algorithm은 prim's algorithm에 비해 시간 복잡도 분석이 복잡합니다.
n = vertex의 개수
m = edge의 개수
1. weight를 비교하여 정렬하는 알고리즘의 시간 복잡도는 m lg m입니다.
2. n개의 disjoint set을 초기화 하는데 걸리는 시간 복잡도는 n 입니다.
3. whlie loop를 도는데 걸리는 시간 복잡도는 m lg n입니다.
이때 m >= n -1이므로
시간복잡도는 \(W(m, n)\,\epsilon\,\theta(m lg m)\)이 됩니다.
하지만 만약에 모든 vertex가 다른 모든 vertex와 연결되어있다면, \(m = \frac{n(n-1)}{2}\,\epsilon\,\theta(n^2)\)이 되버립니다.
따라서 최악의 경우에 크루스칼 알고리즘은
\(w(m, n) \, \epsilon \, \theta(n^2lgn)\)이 되버립니다.
따라서 edge의 개수에 따라서 Kruskal's Algorithm의 시간 복잡도는 차이가 생깁니다.
감사합니다.
지적 환영합니다.