[신장 트리] 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 신장 트리라고 한다. 아래는 원래의 그래프(위)에 대한 부분 그래프(아래), 신장 트리의 예 이다. [크루스칼 알고리즘] 그래프의 간선에 비용이 적혀있다고 하자. 신장 트리의 모든 간선에 대하여, 비용이 합이 가장 적겠끔 하는 신장 트리를 구하는 알고리즘을 최소 신장 트리 알고리즘이라고 한다. 대표적인 최소 신장 트리 알고리즘으로 크루스칼 알고리즘이 있다. 그리디 알고리즘으로 분류된다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선 3, 4 4, 7 4, 6 6, 7 1, 2 2, 6 2, 3 5, 6 1, 5 비용 7 13 23 25 29 34 35 53 75 간선을 하나 하나 체크해가며 그래..
