Introduction
Coddy의 프림 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 1번째.
그래프 알고리즘 시리즈의 마지막 코스에 오신 것을 환영합니다! Kruskal과 마찬가지로, 프림 알고리즘(Prim's Algorithm)은 최소 신장 트리(Minimum Spanning Tree)를 구축합니다. 이는 사이클 없이 모든 정점을 연결하는 가장 저렴한 간선 집합입니다. 두 알고리즘은 서로 다른 경로를 통해 동일한 해답에 도달합니다.
프림 알고리즘은 시작 정점에서 바깥쪽으로 트리를 확장합니다. 각 단계에서 트리에 아직 포함되지 않은 정점과 트리를 연결하는 가장 저렴한 단일 간선을 추가합니다.
그래프는 무방향 가중치 그래프이며, n(정점 0부터 n - 1까지)과 가중치 w인 무방향 간선 u - v에 대한 트리플 [u0, v0, w0, ...]의 평면 배열인 edges로 주어집니다. 우리는 정점 0에서 시작합니다.
시리즈를 마무리해 봅시다!
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
