배경 지식

최소신장트리
그래프의 모든 정점을 포함하면서
가중치의 합이 최소인 트리

가중치
그래프에서 가중치는 간선에 할당된 값으로,
주로 거리, 비용 또는 점수 등을 나타냄

프림 알고리즘

프림 알고리즘은 그래프의 최소 신장 트리를 찾는 데 사용되는 알고리즘
연결 그래프에서 모든 정점을 포함하는 서브그래프를 생성하는 데 사용되며,
그 서브그래프의 가중치 합이 최소가 되도록 함

순서

1. 시작 정점 선택

그래프의 임의의 정점을 선택하여 시작함

2. 인접 정점 탐색

현재 선택된 정점과 연결된 정점들 중에서
최소 가중치를 가지는 간선을 찾기

3. 정점 추가

선택된 간선에 연결된 정점을 신장 트리에 추가

4. 반복

2번과 3번 과정을
모든 정점이 신장 트리에 포함될 때까지 반복

시간 복잡도

프림 알고리즘의 시간 복잡도는 구현 방법에 따라 다름
일반적으로 힙(우선순위 큐)를 사용하여 구현할 경우
O(ElogV)의 시간 복잡도를 가짐

E는 간선의 수
V는 정점의 수

프림 알고리즘이 효과적인 문제 유형

밀집 그래프

점진적 연결 문제