그래픽스 및 게임 엔진 블로그

* 프림알고리즘 시간복잡도 계산프림알고리즘의 시간복잡도 계산은 크루스칼에 비해 상당히 이해하기 까다롭습니다. 크루스칼은 E를 정렬하고 각 edge당 O(1)의 시간복잡도가 생기기 때문에 정렬 시간복잡도 O(ElogE)가 됩니다. 하지만 프림 알고리즘은 O(ElogV)가 됩니다.프림 알고리즘의 동작 구조를 살펴봅시다.  1. 시작 정점을 정합니다 2. 정점에 연결된 모든 방문되지 않은 정점을 힙에 넣습니다 3. 가장 가중치가 작은 값을 힙에서 뺍니다. 4. 그 작은값에 연결된 모든 정점을 다시 힙에 넣습니다. 코드 구조랑 같이 살펴봅시다.#include #include #include #include #include #include using namespace std;const int MAX = 1001..

1. 다익스트라란 ? 음수 사이클이 없는 그래프에서 한 정점에서 모든 정점까지의 최단거리를 구하는 방법입니다.각 단계에서 가장 짧은 경로를 선택하며 진행하기 때문에 그리디의 성질을 가지고 있습니다. 힙으로 그리디 성질을 이용합니다.  각 노드 사이에 가중치가 있고 방향이 있든 없든 상관이 없습니다.https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 기본 코드 구조는 다음과 같습니다. #include #include #include #include // for std::greater#include // for INT_MAXusing ..