개발스토리

최소 비용 신장 트리 - n(> 1) 개의 도시들을 최소한의 비용으로 연결하는 철도망을 새로 구축하려고 한다. - 모든 도시들을 서로 연결하기 위해 도시간 철도를 최소한 (n - 1)개 깔아야 한다. - 각 철도는 두 도시를 연결한다. - 이 철도망들 중에서 철도 노선들의 총 길이가 최소가 되도록 철도망을 구축해야 한다. ■ 신장트리: 연결된, 무방향 그래프안에 있는 모든 정점을 다 포함하면서 트리가 되는 연결된 부분 그래프 ■ 신장트리는 순환을 포함하지 않으며 그래프 안에 있는 모든 정점들을 연결시킨다. ■ 신장트리의 가중치: 모든 간선들의 가중치들의 합 ■ 최소 비용 신장 트리: 최소 가중치를 가진 신장트리 예 : 최소 길이 철도망 억지 기법 알고리즘 ■ 모든 신장 트리를 찾은 후에 그 중에서 최소 ..