인프런 커뮤니티 질문&답변
작성한 질문수
크루스칼 vs 프림
해결된 질문
작성
·
290
0
안녕하세요
강의를 듣다 문득 궁금한게 있어서 질문드립니다.
최소스패닝트리를 구할때
크루스칼, 프림이 있는걸로 알고있는데요..
제가 듣기론 일반적으로 크루스칼이 프림보다 효율적이다 라는 얘기를 들었습니다.
위 말이 맞을까요?
특수한 경우에만 더 효율적인건지 궁금합니다
답변 1
0
김태원
지식공유자
안녕하세요^^
네. 저도 MST 문제는 무조건 크루스칼로 합니다. 코드가 너무 간결하거든요.
일단 크루스칼이 그리디 기법으로 코드가 간결하고 논리도 너무 쉽게 이해가 됩니다. 시간복잡도 측면에서는 큰 차이는 없어보입니다.