• 카테고리

    질문 & 답변

  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

크루스칼 vs 프림

22.09.20 12:49 작성 조회수 142

0

안녕하세요

강의를 듣다 문득 궁금한게 있어서 질문드립니다.

최소스패닝트리를 구할때

크루스칼, 프림이 있는걸로 알고있는데요..

제가 듣기론 일반적으로 크루스칼이 프림보다 효율적이다 라는 얘기를 들었습니다.

위 말이 맞을까요?

특수한 경우에만 더 효율적인건지 궁금합니다

course-thumbnail

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

답변 1

답변을 작성해보세요.

0

김태원님의 프로필

김태원

지식공유자

2022.09.23

안녕하세요^^

네. 저도 MST 문제는 무조건 크루스칼로 합니다. 코드가 너무 간결하거든요.

일단 크루스칼이 그리디 기법으로 코드가 간결하고 논리도 너무 쉽게 이해가 됩니다. 시간복잡도 측면에서는 큰 차이는 없어보입니다.

이 글과 비슷한 Q&A