최소 신장 트리 알고리즘 분석 및 구현
기본 개념
주어진 무방향 그래프 \( G = (V, E) \) 에 대해, 모든 정점이 연결된 부분 그래프 \( G' = (V, E') \) 중에서 간선 가중치의 합이 최소인 트리를 찾는 문제를 최소 신장 트리(Minimum Spanning Tree, MST)라고 한다. 이는 \( |V| \)개의 정점과 \( |V|-1 \)개의 간선으로 구성되며 사이클이 없고 연결되어야 한다.
Prim 알고리즘 (밀도 높은 그래프에 적합)
...
9월 10일 17:17에 게시됨