[알고리즘] 프림 알고리즘(시간 복잡도, 구현방법, 특징)

시간 복잡도

행렬을 사용하였을 경우는 O(n^2)

힙을 사용하였을 경우는 O(nlogn)

 

구현방법

프림 알고리즘은

현재 정점에서 다른 정점에 갈 수 있다면 가는 알고리즘? 이다

거리가 갱신된다면 그 정점으로의 이동이 가능하다

큐에 있는 정점 중 이동 거리가 제일 작은 것의 작은거??로 이동하는 알고리즘

 

 pq에 시작 노드를 넣고 거리를 0으로 초기화

 노드를 꺼내서 방문한 노드라면 pass

 방문하지 않은 노드이고 연결된 노드라면 큐에 넣는다

 모든 노드가 연결될때까지 n-1개의 간선이 생길때까지 연결한다

 

 

특징

노드의 수보다 간선이 더 많을때 사용한다

 

아래 블로그에 이해하기 쉽게 설명되어 있다

https://makefortune2.tistory.com/37

22. 최소신장트리(MST) 프림(Prim) 알고리즘