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

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

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

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

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

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

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

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

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

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

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

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

답변 감사드려요!