크루스칼 VS 프림 파헤치기

먼저. 최소 신장 트리란?

• 최소 신장 트리란, 최소 가중치의 간선을 사용해서 싸이클이 생기지 않으며 모든 정점을 연결한 그래프이다.

앞선 글에서 최소 신장 트리를 구하는 크루스칼 알고리즘에 대해 배웠다.

하지만 또 한가지 최소 신장 트리를 구하는 알고리즘이 있다.

바로 프림 알고리즘이다.

오늘은 크루스칼과 프림 알고리즘을 비교하며 최소 신장 트리를 구하는 과정을 파헤쳐보자.

크루스칼(Kruskal)

동작 원리

• 1. 모든 간선을 가중치 기준 오름차순 정렬한다.
• 2. 최소 가중치 간선부터 순차적으로 선택한다.
     만약, 선택을 함으로써 싸이클이 형성된다면(Find 연산 사용하여 판단)
     해당 간선은 선택하지 않는다
• 3. 이렇게 순차적으로 간선을 선택하면서 정점-1개의 간선이 선택되면 완료.

프림(Prim)

동작 원리

• 1. 임의의 간선을 하나 선택한다.
• 2. 선택한 간선의 정점과 인접한 정점 중에서, 최소 가중치의 간선으로 연결된 정점과 연결
• 3. 모든 정점이 선택되면 완료.

크루스칼 VS 프림

크루스칼은 간선 중심으로 만들어나고, 프림은 정점 중심으로 최소 신장 트리를 만들어나가는 차이점을 가지고 있다.

크루스칼 같은 경우는 매 간선을 선택할때마다, Find 연산으로 싸이클 생성 여부를 판단해야한다.
반면, 프림은 간선이 아닌 시작 정점과 가까운 정점들을 연결하면서 그래프를 구성하기 때문에 싸이클이 생길 수가 없다.

하지만 싸이클을 판단하는 Find 연산은 시간복잡도가 O(1)이기 때문에 큰 영향을 주지 않는다. 크루스칼 알고리즘의 시간복잡도에 가장 많은 영향을 미치는 것은 처음 간선을 오름차순 정렬해주는 부분이다.

시간복잡도

크루스칼의 시간복잡도는 싸이클을 판단하는 O(1)과 간선을 오름차순 정렬하는 연산이 있다. 보통 내장 라이브러리 정렬의 시간 복잡도는 O(NlogN)이므로 만약 그래프의 간선의 갯수가 E라면, 크루스칼의 시간 복잡도는 O(ElogE)이다.
즉, 간선의 갯수에 영향을 받는다.

프림의 시간복잡도는 먼저 모든 정점을 탐색하는 O(V)과 정점마다 힙에서 최소 간선을 찾는 시간복잡도가 O(logV) 이므로 탐색에는 O(VlogV)의 시간이 소요된다. 그리고 각 정점에 연결된 간선을 힙에 추가하는 연산은 한 정점에 최대로 연결될 수 있는 간선 E에, 간선 하나당 최대 정점 N개가 힙에 들어가므로 정렬하는데에 logN이므로 시간복잡도가 O(ElogN)이다.
따라서 O(VlogV + ElogV)인데, 간선(E)는 정점(V)보다 크므로 VlogV는 무시될 수 있다. 따라서 최종 시간 복잡도는 O(ElogV)가 된다.

결론적으로 시간복잡도를 비교해보았을때,

• 1. 간선이 많은 경우에는 프림
• 2. 간선이 적은 경우에는 크루스칼

이라는 결론이 나왔다.