Daily
최소 신장 트리 - 프림 알고리즘, 크루스칼 알고리즘
이 글은 기술면접대비 CS전공 핵심요약집의 일부분인 알고리즘 부분의 내용을 가져와 작성하였습니다.구글 도서 검색 을 통해 전체 페이지 240 중 102페이지를 미리보기 하실 수 있습니다.개인적으로 아래 내용은 위키 백과를 함께 보시길 권장 드립니다.신장 부분 그래프, 프림 알고리즘, 크러스컬 알고리즘최소 신장 트리 (MST, Minimium Spanning Tree)신장 트리는 그래프의 모든 정점을 포함하는 트리를 의미한다. 그중에서 최소 신장 트리는 가중치가 있는 그래프에서 간선의 가중치 총합이 가장 작은 신장 트리를 의미한다.주로 코딩 테스트에서 가중치가 있는 그래프에 대해 최소 신장 트리를 찾는 문제로 등장한다.프림 알고리즘 (Prim algorithm)프림 알고리즘은 그리디 알고리즘으로, 임의의 ..
