Motivation
Coddy의 프림 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 2번째.
Kruskal 알고리즘이 모든 간선을 전역적으로 정렬하고 union-find를 사용하는 반면, Prim 알고리즘은 하나의 성장하는 트리를 유지하며 가장 가까운 외부 정점에 반복적으로 접근합니다.
왜 Prim 알고리즘을 배워야 할까요?
- 밀집 그래프(Dense graphs): 적절한 구조를 사용한 Prim 알고리즘은 간선이 많을 때 효율적입니다.
- 컷 속성(Cut property): 현재 트리에서 나가는 가장 저렴한 간선을 추가하는 것이 왜 항상 안전한지를 보여주는 실질적인 예시입니다.
- 하나의 문제에 대한 두 가지 관점: Prim과 Kruskal을 비교하면 최소 신장 트리(MST)에 대한 이해가 깊어집니다.
그래프의 모든 MST는 동일한 간선 가중치를 공유하므로, Prim과 Kruskal은 항상 동일한 총 가중치를 보고합니다.
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
