다음 방향성 그래프에서 정점 ‘a’부터 시작하는 너비 우선 탐색(Bre… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 15년 1회차
다음 방향성 그래프에서 정점 ‘a’부터 시작하는 너비 우선 탐색(Breath First Search)을 수행하는 경우, 6번째로 방문될 수 있는 정점은? (단, 정점 ‘a’는 첫 번째 방문 노드라고 가정한다)
문제 이미지
1
e
2
f
3
g
4
h
해설

a에서 너비 우선 탐색을 하면 6번째로 방문될 수 있는 정점은 g이다.

BFS는 거리(간선 수) 순으로 방문한다. 거리 1은 a가 가리키는 b, h이고, 거리 2는 b가 가리키는 c, f이다(h는 나가는 간선이 없다). 따라서 둘째부터 다섯째까지는 b, h, c, f 순서 중 하나이며, 6번째는 거리 3인 d 또는 g가 된다.

  • e: d나 g를 거쳐야 도달하는 거리 4의 정점이라 마지막에 방문된다.
  • f: b에서 바로 도달하는 거리 2 정점이라 넷째 또는 다섯째에 방문된다.
  • h: a에서 바로 도달하는 거리 1 정점이라 둘째 또는 셋째에 방문된다.

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

이어서 풀어보기

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