8.프림(Prim) 알고리즘을 이용하여 최소 비용 신장 트리를 구하고 자한다. 다음 그림의 노드 0에서 출발할 경우 가장 마지막에 선택되는 간선으로 옳은 것은? (단, 간선 옆의 수는 간선의 비용을 나타낸다)

해설

[프림 알고리즘과 쿠르스칼 알고리즘] 최소 비용 트리를 구하는 알고리즘 중 정점 기반: 프림. 간선 기반: 쿠르스칼 [프림 알고리즘 작동 순서] 1. 임의의 정점 선택 2. 정점의 간선 중 가장 비용이 낮은 간선을 선택 3-1. 선택된 간선과 연결된 노드가 이미 트리에 있는 노드인 경우 -> 다음으로 큰 간선 선택 3-2. 선택된 간선과 연결된 노드가 트리에 없는 경우 -> 트리에 추가하고 2 반복 [쿠르스칼 알고리즘 작동 순서 1. 모든 간선의 가중치를 오름차순으로 정렬 2. 가장 낮은 비용의 간선 선택 3-1. 선택된 간선과 연결된 노드 2개가 모두 트리에 포함된 경우 -> 해당 간선 폐기 후 다음으로 큰 간선 선택 3-2. 선택된 간선과 연결된 노드 2개 중 1개 이상이 트리에 없는 경우 -> 해당 간선 선택 후 2 반복 [문제 해설] 1. 노드 0과 연결된 간선 중 최소인 (0,5)선택 2. 0, 5와 연결된 간선 중 최소인 (4,5)선택 3. 0, 4와 연결된 간선 중 최소인 (3,4)선택 4. 0, 3, 4와 연결된 간선 중 최소인 (2,3) 선택 5. 0, 3, 4, 2와 연결된 간선 중 최소인 (1,2) 선택 6. 0, 3, 4, 2, 1과 연결된 간선 중 최소인 (1,6) 선택 따라서 0-5-4-3-2-1-6 순서로 트리 구성