[PS/Tip] 크루스칼 알고리즘 VS 프림 알고리즘

크루스칼 알고리즘

• 그래프의 최소 가중치 에지를 차례대로 추가하여 MST를 구현한다.
• 시간 복잡도 : O(E log V)
• 주로 적은 수의 에지로 구성된 희소 그래프(sparse graph)에서 사용된다 

프림 알고리즘

• 그래프의 아무 정점부터 시작하여 MST를 구성한다
• 가장 널리 알려진 시간 복잡도는 O(E + V log V)이다.
• 주로 많은 수의 에지로 구성된 밀집 그래프(dense graph)에서 사용된다