최소 신장 트리 요약

요약

• 가중그래프는 그래프 내 간선이 무게 또는 비용이라 부르는 관련 수치값을 가진 그래프를 말한다.
• 최소신장트리는 가중 그래프의 간선 무게의 합이 최소인 신장트리다.
• 최소신장트리의 두 가지 중요한 속성인 싸이클 속성과 분할 속성은 MST 알고리즘의 정확성 검증에 사용된다.
• 탐욕법은 일반적인 알고리즘 설계 기법 가운데 하나다. 중요한 요소로는 다양한 선택으로 된 구성과 최대화 또는 최소화해야 할 목표가 있으며, 탐욕적 속성이 있는 문제에 적용할 경우 잘 맞는다.
• MST를 구하는 Prime-Jarnik, Kruskal, Baruvka 알고리즘은 최악실행시간이 O(mlogn)으로 동일하지만 외부 데이터구조 사용과 접근 방식에 있어서 상이하다.