yukariko   2년 전

최소 스패닝 트리를 구하는 문제인데

제가 푼 방법은 프림알고리즘에 힙구조를 이용하여 문제를 해결했습니다.

그런데 시간이 매우 느리더군요..

다른 빠른분들이 푸신 방법은 정렬을 이용하여 구해주셨던데

프림알고리즘이 원래 정렬보다 느린건가요?

아니면 제가 구현한 프림 알고리즘이 느린걸까요?

제가 그래프쪽은 힘들어서 후자일거같은데

혹시 프림 알고리즘으로 빠르게 해결하신분이 있으신지 궁금합니다.

chiller123   2년 전

최소 스패닝 트리를 구하는 또다른 알고리즘으로 크루스칼 알고리즘이 있습니다.

이 알고리즘에서는 가중치가 작은 Edge부터 보기 시작하는데, Yukariko님께서 보신 코드는 이 알고리즘을 사용한 코드 일겁니다.

yukariko   2년 전

그렇군요 제가 그래프 알고리즘 공부가부족해서 잘 몰랐습니다..

제가 푼 그래프 문제가 이거랑 네트워크 연결 문제였는데, 여기서도 빠른소스는 다 크루스칼 알고리즘이더라구요.

크루스칼 알고리즘이 일반적으로 프림보다 더 빠른걸까요?

chiller123   2년 전

제가 알기로는, 일반적으로 그래프가 Dense 한 경우에는 프림이, 그렇지 않은 경우는  크루스칼이 성능이 좋은 것으로 알고있습니다.

yukariko   2년 전

아하 그렇군요 좋은답변 감사합니다 ㅎㅎ

pl0892029   2년 전

크루스칼 알고리즘은 간선 정렬하는 과정이 제일 오래걸리고, 최소 신장 트리를 구현하는 과정은 O(VlogV+E)에 수렴합니다. 여기서 VlogV는 유니온-파인드를 수행할 때 발생할 수 있는 최악의 합병시간이라 보시면 되겠습니다.

프림 알고리즘은 다익스트라와 동일합니다. O(ElogV) 입니다. 하지만 logV는 자료구조의 성능에 크게 영향을 받습니다. (STL의 set 혹은 map은 성능이 느린 편이고... Priority_queue를 이용한다면 중복되는 정점들이 원소로 삽입되어 있기 때문에 원소의 수가 최대 E에 가깝게 팽창한다고 합니다.)

둘의 시간복잡도는 크루스칼 = O(ElogE), 프림 = O(ElogV) 라  하지만, 실제 수행되는 것을 들여다보면, 자료구조에 크게 의존하지 않는 크루스칼이 더 "빠를수도" 있다. 라는것만 눈여겨보시면 될듯합니다. ㅋㅋ

yukariko   2년 전

아 자료구조에 따라 성능이 달라져서 프림이 느려졌던거군요..

제가 힙을 사용하면서도 약간 주저했던것이 있엇는데 바로 이것이 이유였나 봅니다.

답변 감사드려요!

댓글을 작성하려면 로그인해야 합니다.