그림 6-26은 현재 정점이 1인 스택 프레임으로 돌아온 모습입니다. 이제 블로킹되어 있던 부분부터 다시 함수가 실행됩니다. for 문 도중에 있었지요. 그런데 adj[1]={0, 2} 모두 방문한 상태이므로 for 문이 끝나면서 함수가 종료됩니다. 함수가 종료되면 스택 프레임이 사라지므로 정점 1을 방문하기 이전 정점인 정점 2로 돌아올 수 있지요.

▲ 그림 6-26 DFS 4

그림 6-27에서는 현재 정점이 다시 시작 정점인 2로 돌아왔습니다. adj[2]={1, 3}에서 정점 1 방향으로 끝까지 따라갔다가 온 셈입니다. 이제 남은 방향으로 쭉 따라가야 합니다. 인수를 정점 3으로 하여 다시 __dfs_recursion 메서드를 호출합니다.

▲ 그림 6-27 DFS 5