문제
다음 중 그래프에서 최소 신장 트리(Minimum Spanning Tree)를 구하는 알고리즘으로 가장 옳은 것은?
① 다익스트라(Dijkstra) 알고리즘 ② 플로이드-워셜(Floyd-Warshall) 알고리즘 ③ 크러스칼(Kruskal) 알고리즘 ④ 벨만-포드(Bellman-Ford) 알고리즘
정답
3번
해설
크러스칼 알고리즘은 그래프의 모든 간선을 가중치 순으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 최소 신장 트리를 구성하는 알고리즘이다. ① 다익스트라 알고리즘은 단일 출발점에서 다른 모든 정점까지의 최단 경로를 구한다. ② 플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구한다. ④ 벨만-포드 알고리즘은 음수 가중치가 있는 그래프에서 최단 경로를 구한다.