문제
그래프에서 모든 정점을 방문하는 최소 비용 신장 트리를 구하는 알고리즘 중, 간선을 가중치 순으로 정렬한 후 사이클을 형성하지 않는 간선을 선택하는 방식은?
① 다익스트라 알고리즘 ② 크루스칼 알고리즘 ③ 프림 알고리즘 ④ 벨만-포드 알고리즘
정답
2번
해설
크루스칼 알고리즘은 모든 간선을 가중치 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 하나씩 선택하여 최소 신장 트리를 구성한다. 다익스트라와 벨만-포드는 최단 경로 알고리즘이고, 프림은 정점 기반으로 신장 트리를 확장한다.