크루스칼 알고리즘이나 프림 알고리즘 모두 탐욕 알고리즘(greedy algorithm)의 한 종류입니다. 이 절에서 탐욕 알고리즘을 간단히 다루어 보겠습니다. 크루스칼과 프림, 다음 장에서 다룰 데이크스트라 모두 탐욕 알고리즘 기반입니다.

탐욕 알고리즘을 간략히 정의하면, 매 단계마다 항상 최선일 것 같은 선택을 하면 전체적으로도 최선의 선택을 하게 된다는 알고리즘입니다. 지역 최적해(locally optimal solution)를 합쳐 나가면 전역 최적해(globally optimal solution)에 도달한다는 것입니다. 탐욕 알고리즘은 성능이 매우 뛰어나지만 항상 옳은 해를 주지는 못하고 두 가지 제약 조건을 만족해야만 사용할 수 있습니다. 따라서 탐욕 알고리즘을 적용하려면 이 두 가지 제약 조건을 반드시 먼저 검증하고 사용해야 합니다. 이 두 가지 제약 조건을 탐욕 특성(greedy properties)이라고 합니다.

1. 최적 부분 구조(optimal substructure): 어떤 전체 문제에 대한 최적해는 부분 문제(subproblem)에 대한 최적해를 포함하고 있습니다.

2. 탐욕 선택 특성(greedy choice property): 부분적으로 최적의 선택을 계속하면 전역적으로 최적해에 도달할 수 있습니다.

우리가 알아보려는 MST 알고리즘은 모두 이 탐욕 특성을 만족합니다.