[Algorithm] Minimum Spanning Trees (2)

저번 글에서 다뤘던 Prim's Algorithm이 골라진 정점들에서 연결된 간선들중 가장 최소 가중치 값을 가지는 간선을 찾으면서 진행하는 알고리즘이였다면 이번 시간에 배우는 Kruskal's Algorithm은 각 간선을 가중치 기준으로 오름차순 정렬 한 뒤 간선의 두 정점이 서로 다른 집합일 경우 합치고, 같은 집합에 있다면 사이클이 발생하므로 합치지 않는다.

이 경우 (v1,v2) 집합과 (v3,v5)집합이 (v1,v3)을 통해 합쳐지고 이 합쳐진 (v1,v2,v3,v5) 집합이 (v3,v4)를 통해 합쳐지며 minimum spanning tree를 이룬다.

이 krusukal's alogirhtm의 optimality를 증명 하는 방법은 prim algorithm과 유사한 방법으로 진행한다.

 

1번 증명은 prim과 거의 똑같으므로 설명은 생략하겠다.

 

2번또한 비슷한데.

minimun spanning tree F'에 F'에 포함되어 있지 않은 간선 e를 추가 할 경우 반드시 하나의 cycle이 생기는데 이때 이 cycle에 참여하는 또다른 간선 e'을 제거할 경우 이 집합 F' + e - e'은 minimum spanning tee를 만족한다.(궁금증이 생기거나 이해가 제대로안되었을 경우 댓글에 남기면 자세히 알려드리겠습니다)

 자 그러면 prim과 kruskal의 차이는 무엇인가?

 

우선 시간 복잡도 측면에서 차이가 난다. 프림의 경우 O(n^2)의 시간복잡도를 가지며 이는 피보나치 힙을 쓸경우 m+nlogn까지 낮출 수 있다. 우리는 간단하게 n^2으로 놓고 보겠다.

 

크루스컬의 경우는 mlogm의 시간 복잡도를 가진다. (이때 n은 vertex의 개수, m은 edge의 개수이다)

 

이 경우 간선의 개수에 따라 알고리즘의 선택이 달라지는데. 만약 edge의 개수가 최소 개수인 n-1개 일 경우 이때 크루스컬은 nlogn정도의 시간복잡도를 가지므로 크루스컬 알고리즘이 더 유용하다 

만약 간선의 개수가 최대인 n(n-1)/2 일 경우 (이는 한 정점이 다른 모든 정점으로 이동가능한 간선을 소유하고 있는 complete graph) 이때 크루스컬은 (n^2 log n)에 가까워 지므로 이때는 n^2인 프림이 더 유용하다. 

 

다음 장에서는 허프만 코드에 대해 알아보겠다.