프림 MST 시각화
정점 기반으로 최소 신장 트리를 구성하는 프림 알고리즘을 단계별로 학습하세요
그래프★★☆
속도
1 / 1MST 간선: 0총 가중치: 0
MST 간선 검사 중 후보 미방문
프림이 정점을 확장하며 MST를 구성하는 과정을 관찰하세요.
프림이 정점을 확장하며 MST를 구성하는 과정을 관찰하세요.
프림 알고리즘이란?
임의의 정점에서 시작하여 현재 트리에 연결된 간선 중 최소 가중치를 반복적으로 선택해 최소 신장 트리(MST)를 구성하는 그리디 알고리즘입니다.
사용 방법
- 1그래프를 생성하고 시작 정점을 선택하세요
- 2실행 버튼으로 단계별 MST 구성 과정을 관찰하세요
- 3후보 간선(노란색)과 선택 간선(초록색)을 구분하세요
- 4크루스칼과 결과를 비교해보세요
동작 원리
- 1시작 정점을 MST에 추가하고 인접 간선을 우선순위 큐에 삽입합니다
- 2큐에서 최소 가중치 간선을 꺼내 반대편 정점이 미방문이면 MST에 추가합니다
- 3새로 추가된 정점의 인접 간선을 다시 큐에 삽입합니다
- 4모든 정점이 MST에 포함될 때까지 반복합니다 — O(E log V)
실무 활용
- •네트워크 설계 — 최소 비용으로 모든 노드를 연결하는 케이블 배치
- •도로/파이프라인 설계에서 최소 건설 비용 산출
- •클러스터링 알고리즘(Single-linkage)의 기반
- •VLSI 회로 설계의 배선 최적화
비슷한 알고리즘
- •크루스칼 — 간선 기반 MST, 희소 그래프에 유리. 프림은 밀집 그래프에 유리
- •보루프카 — 병렬 MST 구성 가능, 분산 환경에 적합
- •다익스트라 — 유사한 구조이나 최단 경로용. 프림은 MST용
학습 팁
- •크루스칼과 동일한 그래프에서 실행하여 결과가 같은지 확인하세요
- •우선순위 큐의 동작을 관찰하며 그리디 선택을 이해하세요
- •시작 정점을 바꿔도 MST 가중치 합이 동일함을 확인하세요
자주 묻는 질문
Q. 크루스칼과 어떤 차이?
A. 프림은 정점 기반(밀집 그래프에 유리), 크루스칼은 간선 기반(희소 그래프에 유리)입니다.
Q. 시작 정점에 따라 결과가 달라지나?
A. MST의 간선 구성은 달라질 수 있지만 총 가중치는 항상 동일합니다.