목록krukasal (1)

데이터 분석 기술 블로그

최소 비용 신장 트리(MST)

1. 최소 신장 트리(MST)그래프에서 최소 비용 문제1) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리2) 두 정점 사이의 최소 비용의 경로 찾기신장 트리n 개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리최소 신장 트리(Minimum Spanning Tree)무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리2. Prim 알고리즘하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식1) 임의 정점을 하나 선택해서 시작2) 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택3) 모든 정점이 선택될 때까지 1), 2) 과정을 반복서로소인 2개의 집합(2 disjoi..
알고리즘 2024. 7. 10. 09:00
이전 Prev 1 Next 다음