etc.
-
[자료구조] 최소 비용 신장 트리etc. 2022. 6. 6. 21:58
신장트리 n개의 정점으로 이루어진 무방향 그래프에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리 - 깊이 우선 신장 트리 : 깊이 우선 탐색을 이용하여 생성된 신장 트리 - 너비 우선 신장 트리 : 너비 우선 탐색을 이용하여 생성된 신장 트리 최소 비용 신장 트리 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장트리 최소 비용 신장 트리를 만드는 알고리즘 - Kruskal 알고리즘 - Prime 알고리즘 Kruskal 알고리즘 Ⅰ 가중치가 높은 간선을 제거 1. 그래프에서 모든 간선을 가중치에 따라 내림차순으로 정리 2. 그래프에서 가중치가 가장 높은 간선을 제거 - 이때 정점을 그래프에서 분리시키는 간선을 제거할 수 없으므로 그 다음으로 가중치가 높은 간선 제거 ..