시작 정점이 A일 때, 다음 그래프에 대한 깊이 우선 탐색(DFS : … | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지

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

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

DFS는 알파벳 순으로 가장 앞선 미방문 인접 정점으로 계속 내려가므로 A→B→C→F→H→G→D→E로 진행하고, E에서 더 갈 곳이 없어 H까지 되돌아간 뒤 I를 방문한다.

BFS는 A의 인접 정점 B, D, E를 먼저 방문하고, 이어서 C(B에서), G(D에서), F(C에서), H(G에서), I(F에서) 순으로 방문한다.

  • DFS가 G 다음에 E, D 순으로 방문한다는 순서: G의 미방문 인접 정점 중 알파벳 순으로 D가 E보다 앞서므로 D를 먼저 방문해야 한다.
  • BFS가 A, B, C, D, E 순으로 진행한다는 순서: C는 A와 인접하지 않고 B를 거쳐 발견되므로, A와 직접 인접한 D, E보다 먼저 방문될 수 없다.

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

이어서 풀어보기

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