Kruskal1 [알고리즘] Prim`s algorithm. MST 구하는 2번째 방법. 프림 반갑습니다. 이번엔 O(ElogV) 시간복잡도를 가지는 Prim알고리즘에 대해서 알아보겠습니다. 이건 음.. heap을 알아야 하는데, 힙구조를 가지는 priority_queue를 사용할 수 있으면 좋습니다. 없으면 kruskal이 구현하기 더 낫습니다. Kruskal VS Prim 결과부터 말하면 Edge가 많으면 Prim, Edge가 적으면 Kruskal이 좀 더 좋습니다. (이론상) Kruskal은 sort과정에 O(ElogE)이 피할 수 없기에 E에 영향을 받고, Prim은 O(ElogV)입니다. 이미 방문된 지점은 다시 방문되지 않기에 pq의 push나 pop과정이 없어서 그렇습니다. 근데 MST를 찾는다는건 기본적으로 V < E니까 쓰겠죠...? 근데 그냥 편한대로 합시다. .. 2021. 10. 2. 이전 1 다음 728x90