알고리즘 이론/프림 알고리즘1 프림 알고리즘(Prim's algorithm) 1. 프림 알고리즘(Prim's algorithm): 크루스칼 알고리즘과 다르게(전체 간선을 정렬한 후 하나의 간선부터 시작), 하나의 특정 노드를 정하고, 연결된 간선 중 가중치가 가장 작은 간선을 선택하며 길을 확장하는 알고리즘 (예, 스타 크래프트 게임) - 크루스칼 알고리즘과 공통점: 둘다 탐욕 알고리즘을 구현함 2. 시간 복잡도: 최악의 경우(while문에서 모든 간선을 돌고, 최소 힙 구조를 이룬다면) O(E logE), - 개선된 시간 복잡도: O(E logV) 2020. 10. 12. 이전 1 다음