[알고리즘] 크루스칼, 프림 어떤 알고리즘이 더 좋아요?

[알고리즘] 최소 신장 트리 - 크루스칼 알고리즘과 Union Find, 백준 1197번 C++ 풀이

 

[알고리즘] 최소 스패닝 트리 - 프림 알고리즘

크루스칼과 프림이 뭔지 모른다면 위의 두 글을 읽고오자.

---

 

각 알고리즘의 장단점과 시간복잡도를 PS 관점에서 정리해보자.

크루스칼 알고리즘

장점

1. 구현이 간단하다. 정렬 한 번과 Union-Find 자료구조만 있으면 된다.
2. 우선순위 큐가 필요 없어 메모리 사용이 효율적이다.
3. 간선 중심 접근으로, 특히 그래프가 sparse한 경우 효율적이다.
4. 정렬 한 번으로 모든 작업을 처리할 수 있어 대부분의 PS 문제에서 충분히 빠르다.
   • 이 부분이 상당히 중요하다. PS에서 다루는 대부분의 그래프 크기에서는 크루스칼이 프림보다 빠르다.
   • Prim의 우선순위 큐가 항상 전체 edge의 일정 비율 이하만을 포함한다 한들, 정렬 1번이면 되는 Kruskal과 속도 승부를 볼 만큼 그래프가 커질 일은 PS에선 거의 없다.
   • 참고 (https://www.acmicpc.net/board/view/141785)

단점

1. 간선이 매우 많은 밀집 그래프에서는 정렬에 시간이 많이 걸릴 수 있다.

프림 알고리즘

장점

1. 정점 중심 접근으로, 밀집 그래프에서 이론적으로는 더 효율적일 수 있다.
2. 시작 정점을 선택할 수 있어 부분적 MST 구성에 유리하다.

단점

1. 우선순위 큐를 사용하므로 구현이 크루스칼보다 복잡하다.
2. 우선순위 큐 관리에 추가적인 시간과 메모리가 필요하다.

결론적으로 간선 가중치를 기준으로 정렬이 필요한 경우, 시간 복잡도가 정말 빡빡한 경우 크루스칼이 유리하다.

그러나 특정 정점에서 시작하는 MST가 필요한 경우, 매우 큰 밀집 그래프를 다룰 때 프림이 적합하다.