다음 그래프를 너비 우선 탐색(Breadth First Search B… | [계리직 컴퓨터일반] 10년 1회차 기출문제 상세 페이지
1[계리직 컴퓨터일반] 10년 1회차
다음 그래프를 너비 우선 탐색(Breadth First Search BFS), 깊이 우선 탐색(Depth First Search DFS) 방법으로 방문할 때 각 정점을 방문하는 순서로 옳은 것은? 단, 둘 이상의 정점을 선택할 수 있을 때는 알파벳 순서로 방문한다. (순서대로 BFS, DFS)
1
A-B-F-C-E-D, A-B-C-D-E-F
2
A-B-C-D-E-F, A-B-F-C-E-D
3
A-B-F-C-D-E, A-B-C-D-E-F
4
A-B-C-D-E-F, A-B-C-D-F-E
해설
BFS는 A-B-F-C-D-E, DFS는 A-B-C-D-E-F 순서로 방문한다.
그래프의 간선은 A-B, A-F, B-C, B-F, C-D, C-F, D-E, D-F, E-F 이다. BFS는 A의 이웃 B, F를 먼저 방문하고, 이어서 B의 이웃 C, F의 이웃 D, E를 알파벳 순으로 방문한다.
DFS는 A에서 B, B에서 C, C에서 D, D에서 E로 계속 깊이 들어간 뒤 E의 미방문 이웃 F를 마지막에 방문한다.
- BFS를 A-B-F-C-E-D로 둔 배열: F의 이웃 중 D가 E보다 알파벳 순으로 앞서므로 D를 먼저 방문한다.
- BFS를 A-B-C-D-E-F로 둔 배열: 너비 우선이면 A와 인접한 F가 C·D·E보다 먼저 방문된다.
- DFS를 A-B-C-D-F-E로 둔 배열: D의 미방문 이웃 E, F 중 알파벳 순으로 E를 먼저 방문한다.
오류나 개정된 내용이 보이면 알려주세요