스패닝 트리(Spanning Tree) 그래프의 스패닝 트리란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프입니다. 위의 사진처럼 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면 스패닝 트리라고 부를 수 있습니다. 스패닝 트리는 V개의 모든 정점을 연결하는 간선의 수는 V-1개입니다. 최소 스패닝 트리(MST) 최소 스패닝 트리란 원본 그래프에서 신장 트리를 만들 수 있는 경우의 수들 중 최소의 간선 비용을 들여서 만들 수 있는 신장트리를 최소 신장 트리라고 합니다. 위의 그림을 예시로 보면, 빨간색 선으로 이루어진 신장 트리르릴 만드는 데 비용이 13이 듭니다. 이는 위의 그래프에서 합을 구할 수 있는 경우의 수중 가장 적은 비용을 나타냅니다. 이렇게 최소 신장 트리를 효율적으로 찾..