← 질문 목록
#361깊이 0
크루스칼과 프림 알고리즘은 언제 구분하여 사용하는가?
자료구조 · 알고리즘
답변 연습
내 답변 적어보기접힘
이 브라우저에 자동 저장 · 0자
모범답안 확인하기내 답변 뒤에 열어보세요
간선이 적은 희소 그래프에서는 크루스칼을 쓰고 간선이 많은 밀집 그래프에서는 프림을 쓴다.
| 기준 | 크루스칼 알고리즘 | 프림 알고리즘 |
|---|---|---|
| 주 탐색 대상 | 간선 중심 | 정점 중심 |
| 시간 복잡도 | O(E log E) | O(E log V) |
| 유리한 그래프 | 희소 그래프 | 밀집 그래프 |
크루스칼은 가중치가 작은 간선부터 선택하며 사이클 형성 여부를 확인한다. 간선 정렬 비용이 전체 시간을 좌우하므로 간선 수가 적을수록 빠르게 동작한다.
프림은 특정 정점에서 출발해 연결된 간선 중 가중치가 가장 작은 것을 고른다. 정점 기준으로 확장하므로 간선 수가 많아도 정점 수가 적다면 탐색 속도를 유지한다.
네트워크 노드를 최소 비용으로 연결하는 문제에서 그래프 구조에 따라 적절한 방식을 선택한다.