신장 트리
그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
최소 신장 트리
최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때
크루스칼 알고리즘
대표적인 최소 신장 트리 알고리즘
그리디 알고리즘으로 분류된다
동작 과정
간선 데이터를 비용에 따라 오름차순으로 정렬
간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다
사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다
모든 간선의 수는 노드 개수 - 1
