[자료구조][알고리즘] Prim's Algorithm(프림 알고리즘)

1. Prim's Algorithm이란?

Prim's Algorithm(프림 알고리즘)은 그래프를 공부할 때 함께 배웠던 minimum cost spanning tree(최소 스패닝 트리)를 구하는 방법 중 하나이다.
이 알고리즘에서는 한 노드에서 시작하여, 그 노드의 edge 중 cycle을 만들지 않으면서 cost가 작은 노드 순으로 추가하며 트리를 만든다.

2. 예시

위 그림과 같은 그래프가 있다고 하자. 프림 알고리즘에서는 먼저 그래프에서 노드 하나만을 그려놓은 상태에서 시작한다.

1의 edge 중, 가장 cost가 작은 것은 cost가 2인 (1, 2) edge이다. 따라서 이 edge를 1에 추가하고, 2 노드를 만들어 연결한다.

1과 2 노드의 edge 중에서는 cost가 7인 (2, 3) edge가 가장 cost가 작으므로, 이 edge를 추가하고, 3 노드를 만들어 연결한다.

1, 2, 3 노드 중 가장 cost가 작은 cost가 4인 (3, 4) edge를 추가하고, 4 노드를 만들어 연결한다.

이렇게 1, 2, 3, 4 노드를 연결한 후, 가장 cost가 작은 edge를 고르면 cost가 8인 (1, 3) edge를 고르게 된다. 그러나 이 edge는 이 그래프에 cycle을 만들게 되므로, 추가하지 않는다. 마찬가지로 cost가 9인 (2, 4) edge도 추가하지 않고, cost가 10인 (3, 5) edge를 추가한다. 그리고 5 노드를 만들어 연결한다.

가장 cost가 작은 cost가 6인 (5, 6) edge를 추가하고, 6 노드를 만들어 연결한다.

가장 cost가 작으면서 cycle을 만들지 않는 cost가 14인 (5, 7) edge를 추가하고, 7 노드를 만들어 연결한다.

마지막으로 가장 cost가 작은 cost가 3인 (7, 8) edge를 추가하면 프림 알고리즘을 이용하여 최소 스패닝 트리를 만들 수 있다.

3. 시간복잡도

• Dijkstra's algorithm(다익스트라 알고리즘)을 사용할 경우: $O(n^2)$
• Fibonacci heap을 사용할 경우: $O(e+n\log n)$
  • 모든 최소 스패닝 트리 알고리즘 중 가장 빠르다.