다음 그래프에 대한 너비 우선 탐색(BFS: Breadth First … | [7급 국가직 자료구조론] 20년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 20년 1회차
다음 그래프에 대한 너비 우선 탐색(BFS: Breadth First Search)의 방문 순서는? (단, 시작 정점은 A이고, 인접한 정점들은 알파벳 순서로 방문한다)
문제 이미지
1
A, C, D, E, G, I, B, H, F
2
A, C, D, E, I, G, H, B, F
3
A, C, D, G, B, E, F, H, I
4
A, C, D, G, I, B, E, H, F
해설

BFS 방문 순서는 A, C, D, E, G, I, B, H, F이다.

BFS는 큐를 사용해 가까운 정점부터 방문한다. A의 인접 정점 C, D, E를 알파벳 순으로 넣고, C에서 G, D에서 I, E에서 B와 H를 차례로 추가한다.

마지막으로 B에서 아직 방문하지 않은 F가 추가되어 탐색이 끝난다.

  • A, C, D, E, I, G, … — C가 D보다 먼저 꺼내지므로 C의 이웃 G가 D의 이웃 I보다 앞서야 한다.
  • A, C, D, G, B, … — E는 A와 직접 연결된 1단계 정점이므로 G보다 먼저 방문해야 한다.
  • A, C, D, G, I, B, E, … — 역시 1단계 정점 E가 2단계 정점들보다 뒤에 놓여 BFS 순서가 아니다.

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

이어서 풀어보기

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