다음의 인접리스트는 어떤 그래프를 표현한 것이다. 이 그래프를 정점 A… | [9급 지방직 컴퓨터일반] 16년 1회차 기출문제 상세 페이지
1[9급 지방직 컴퓨터일반] 16년 1회차
다음의 인접리스트는 어떤 그래프를 표현한 것이다. 이 그래프를 정점 A에서부터 깊이 우선 탐색(depth first search)할 때, 정점이 방문되는 순서로 옳은 것은?
- 정점A → B → C → D → null
- 정점B → A → E → F → null
- 정점C → A → F → null
- 정점D → A → F → null
- 정점E → B → G → null
- 정점F → B → C → D → G → null
- 정점G → E → F → null
1
A → B → C → D → F → G → E
2
A → D → C → B → F → E → G
3
A → B → C → D → E → F → G
4
A → B → E → G → F → C → D
해설
정점 A에서 깊이 우선 탐색하면 A → B → E → G → F → C → D 순으로 방문한다.
DFS는 현재 정점의 인접 리스트를 앞에서부터 보며 방문하지 않은 첫 정점으로 즉시 내려간다. A에서 B, B의 리스트(A, E, F)에서 E, E의 리스트(B, G)에서 G, G의 리스트(E, F)에서 F로 간다. F의 리스트(B, C, D, G)에서 C를 방문하고, C는 더 갈 곳이 없어 F로 되돌아와 D를 방문한다.
- A → B → C → D → F → G → E는 B를 방문한 뒤 B의 미방문 이웃 E로 내려가지 않고 A의 다음 이웃 C로 넘어가므로 깊이 우선이 아니다.
- A → D → C → B → F → E → G는 A의 인접 리스트 첫 정점인 B를 건너뛰고 D부터 방문한다.
- A → B → C → D → E → F → G는 A의 이웃 B, C, D를 먼저 모두 방문한 뒤 다음 단계로 넘어가는 너비 우선 탐색(BFS)의 방문 순서이다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.