최소 신장 트리: 비음수 가중치 무방향 그래프
프림 알고리즘 (인접 행렬 기반)
다익스트라 알고리즘과 유사하지만, 거리 업데이트 대상이 다른 점이 핵심이다. 프림은 현재 신장 트리에 포함된 정점들과 연결된 간선 중 최소 가중치를 선택하여 확장한다.
크루스칼 알고리즘
Union-Find 자료구조를 활용하며, 모든 간선을 가중치 기준으로 오름차순 정렬한다. 두 정점이 이미 같은 연결 컴포넌트에 속해 있으면 간선 ...
7월 6일 19:29에 게시됨