greedy approach를 신장트리로 시각화할 수 있다. 신장트리는 정점이 서로 연결되어있고 방향이 없는 그래프에서 순환 경로가 없도록 엣지를 제거하되 모든 정점이 그래프에 포함되도록 연결한 부분 그래프이다. 여기서 비용이 최소가 되도록 연결한 그래프(신장트리)를 최소비용 신장트리라고 한다. 글로만 읽으면 무슨 말인지 이해가 잘 안될테니 그림으로 이해해보자. 아래 그림은 신장트리의 한 예를 보여준다. 위 그림의 신장트리가 과연 최소신장트리일까? 오른쪽의 신장트리가 왼쪽의 그래프에서 도출될 수 있는 그래프들 중 비용이 가장 적은 그래프일까? 그렇지 않다. 비용이 더 작은 엣지들을 사용해서도 충분히 모든 정점들을 이으면서 순환 경로가 없도록 그래프를 만들 수 있다는 것을 알 수 있다. 하지만 이는 위의 ..