프림(Prim) 알고리즘을 적용하여 다음 그래프의 정점 A에서 시작하는… | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지

프림 알고리즘으로 선택되는 마지막 정점은 C이다.
매 단계 트리와 바깥 정점을 잇는 최소 간선을 고르면 B(7), D(8), E(4), H(3) 순으로 붙는다. 이때 남은 후보는 B–F 9, D–C 10, H–C 11, H–G 14이므로 F가 9로 선택된다.
이어서 F–G 1로 G가 붙고, 마지막으로 G–C 2로 C가 선택된다.
F: 다섯 번째로 선택되며 B–F 간선 9가 D–C 10보다 작아 C보다 먼저 붙는다.
G: F가 들어온 직후 가중치 1인 F–G 간선으로 여섯 번째에 선택된다.
H: E가 들어온 직후 E–H 간선 3으로 네 번째에 선택된다.