[PS/Tip] 크루스칼 알고리즘 VS 프림 알고리즘
·
PS/Tip
크루스칼 알고리즘그래프의 최소 가중치 에지를 차례대로 추가하여 MST를 구현한다.시간 복잡도 : O(E log V)주로 적은 수의 에지로 구성된 희소 그래프(sparse graph)에서 사용된다 프림 알고리즘그래프의 아무 정점부터 시작하여 MST를 구성한다가장 널리 알려진 시간 복잡도는 O(E + V log V)이다.주로 많은 수의 에지로 구성된 밀집 그래프(dense graph)에서 사용된다