다음 그래프에 대한 깊이 우선 탐색(depth first search)… | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지

가능한 방문 순서는 D, F, E, B, A, C이다. 그림의 간선은 C→A, A→B, A→D, B→F, C→F, D→E, D→F, E→B, E→F이다.
D에서 출발해 F를 방문하면 F는 나가는 간선이 없어 D로 돌아오고, 다음 인접 정점 E를 방문한다. E→B로 B를 방문한 뒤 B의 인접 정점 F는 이미 방문했으므로 되돌아온다. D에서 도달할 수 없는 A, C는 새 시작 정점으로 차례로 방문하면 되므로 유효한 DFS 순서다.
A, B, F, C, D, E: F에서 A로 되돌아오면 A의 미방문 인접 정점 D를 먼저 방문해야 하는데 C로 넘어가므로 불가능하다.
C, A, B, D, E, F: B의 인접 정점 F가 미방문인데 B에서 F로 가지 않고 D로 넘어가므로 불가능하다.
E, F, A, B, D, C: F에서 E로 되돌아오면 E의 미방문 인접 정점 B를 먼저 방문해야 하는데 A로 넘어가므로 불가능하다.