다음 그래프(graph)에 대하여 깊이 우선 탐색(DFS, depth … | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 23년 1회차
다음 그래프(graph)에 대하여 깊이 우선 탐색(DFS, depth first search)을 하려고 한다. 시작 정점(vertex)이 B일 때, 정점 I는 몇 번째에 방문하는가? (단, B가 첫 번째 방문 정점이고, 탐색 시 인접한 정점들은 알파벳 오름차순으로 방문한다)
1
4
2
5
3
8
4
9
해설
B에서 알파벳 오름차순으로 깊이 우선 탐색을 하면 B → E → A → C → I 순으로 진행되어, 정점 I는 다섯 번째로 방문된다.
B의 인접 정점 E·F·G 중 E로 먼저 내려가고, E의 인접 정점 A·C·I 중 A를 방문한 뒤 막혀 E로 되돌아온다. 이어 C를 방문하면 C의 미방문 인접 정점 I로 바로 내려간다.
전체 방문 순서는 B, E, A, C, I, F, D, H, G이다.
- 네 번째로 방문되는 정점은 I가 아니라 C이다.
- 여덟 번째로 방문되는 정점은 F → D 다음의 H이다.
- 아홉 번째(마지막)로 방문되는 정점은 G이다.
오류나 개정된 내용이 보이면 알려주세요