최소 신장 트리 알고리즘 분석 및 구현
기본 개념
주어진 무방향 그래프 \( G = (V, E) \) 에 대해, 모든 정점이 연결된 부분 그래프 \( G' = (V, E') \) 중에서 간선 가중치의 합이 최소인 트리를 찾는 문제를 최소 신장 트리(Minimum Spanning Tree, MST)라고 한다. 이는 \( |V| \)개의 정점과 \( |V|-1 \)개의 간선으로 구성되며 사이클이 없고 연결되어야 한다.
Prim 알고리즘 (밀도 높은 그래프에 적합)
...
9월 10일 17:17에 게시됨
최소 스패닝 트리 알고리즘 비교: Kruskal, Prim, Boruvka
Kruskal 알고리즘
희소 그래프(Sparse Graph)에 적합한 크루스칼 알고리즘은 간선 기반의 탐욕적 접근 방식을 사용한다. 모든 간선을 가중치 기준으로 오름차순 정렬한 후, 사이클을 만들지 않는 한도 내에서 순차적으로 선택한다. 이때 연결 여부는 유니온-파인드(Union-Find) 자료구조로 관리한다.
n개의 정점이 주어졌을 때, 최소 스패닝 트리는 정확히 n-1개의 간선으 ...
6월 17일 18:25에 게시됨