신장트리란? 신장트리란 연결 그래프의 부분 그래프이다. 그래프는 속도는 높지만 사이클이 존재하므로 비용이 많이 들게 된다. 신장트리는 사이클이 존재해서는 안되므로 속도측면에서는 그래프보다 뒤떨어질 수 있어도 비용 측면에서 그래프보다 우세하다. 정리해보면 신장트리에서 모든 노드는 적어도 하나의 간선에 연결되어 있어야 하며 그 대신에 사이클이 형성되면 안된다. 최소 비용 신장 트리란? 그래프의 간선에 가중치가 부여된 그래프를 가중치 그래프 또는 네트워크라고 한다. 이때 가중치란 비용이나 거리를 의미하는 값이 될 수 있다. 가중치가 부여된 무방향 그래프의 신장 트리 비용은 신장트리를 구성하는 모든 간선의 비용을 합한 것이다. 여기서 말하는 최소 비용 신장트리는 트리를 구성하는 간선들의 가중치를 합한 것이 최소..
