정의

프림은 한 노드에서 출발해 "트리에 가장 싸게 붙는 간선"을 우선순위 큐로 골라 한 칸씩 넓혀가는 최소 신장 트리 알고리즘입니다.

핵심 특성

• ✓우선순위 큐 사용: 트리에 붙일 수 있는 간선 중 가장 싼 것을 먼저 꺼냅니다.
• ✓그리디 방식: 매 단계 트리를 가장 싸게 한 노드 더 키웁니다.
• ✓간선 비교 기준이 "노드 1개를 잇는 간선" 하나 — 다익스트라의 "시작점까지의 거리 합"과 다릅니다.
• ✓밀집 그래프(E가 많을 때)에서 크루스칼보다 유리한 경우가 많습니다.

시간 복잡도