[ Algorithm / 알고리즘 ] Prim's Algorithm ( 프림 알고리즘 )

Prim's Algorithm 이란

Prim's Algorithm은 무향 연결 그래프가 주어질 때, 최소 비용 신장 트리 을 찾는 알고리즘

 

Prim's Algorithm 동작

1️⃣ 임의의 node ( 시작 정점 )을 선택하여 MST ( 최소 비용 신장 트리 ) 집합에 추가

2️⃣ 인접 node 중 최소 비용의 edge로 연결된 node 선택

👉 이 과정을 모든 node를 선택할 때 까지 반복 ‼️

 

Prim's Algorithm 시간 복잡도

• 주 반복문이 node의 수 n번 반복 ❌ 내부 반복문이 n번 반복
  • 👉 시간 복잡도는 O(n^2)