신장트리 (Spanning Tree) 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립조건이기도 하다. 예를 들어 다음과 같은 그래프가 있다고 하자. 위의 그래프에서 가능한 신장 트리는 다음과 같다. (여러개 존재 가능) 다음은 신장 트리가 될 수 없다. 사이클이 존재하기 때문이다. 다음도 신장 트리가 될 수 없다. 노드 2를 포함하고 있지 않기 때문이다. 최소 신장 트리 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘을 말한다. 최소 신장 트리의 간선의 개수는 '노드의 개수 - 1'이다. 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 ..
