다음 비용 그래프에서 최소 비용 신장 트리를 구하고자 한다. Prim … | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 11년 1회차
다음 비용 그래프에서 최소 비용 신장 트리를 구하고자 한다. Prim 알고리즘을 이용하여 최소 비용 신장 트리를 구할 때, 4번째로 연결되는 간선(edge)으로 옳은 것은? (단, 시작 노드는 A이다)
문제 이미지
1
(A, D)
2
(B, E)
3
(E, F)
4
(F, C)
해설

A에서 시작한 Prim 알고리즘의 네 번째 간선은 (E, F)이다.

Prim은 이미 선택된 정점 집합과 바깥 정점을 잇는 간선 중 최소 비용 간선을 하나씩 추가한다. 선택 순서는 (A, B) 5 → (B, E) 20 → (E, D) 10 → (E, F) 30 이다.

  • (A, B) 5: 첫 번째로 연결되는 간선이다.
  • (B, E) 20: 두 번째로 연결되는 간선이다.
  • (A, D): D는 세 번째 단계에서 더 싼 (E, D) 10으로 연결되므로 선택되지 않는다.
  • (F, C) 15: F가 들어온 다음인 다섯 번째에 연결되는 간선이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 11년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기