그림 2-20에서 깊이 우선 탐색을 추적할 때 노드(방) 0에서 시작하고 이미 방문한 노드는 빨간색, 현재 노드는 분홍색으로 표시한다. 이중선은 탐색 과정에서 손에 쥐고 있는 가상의 실을 표시한다. 테세우스가 했던 것과 마찬가지로 더 나아갈 수 없거나 가서는 안 될 때 되돌아가기 위해 이 실을 사용한다.

아직 방문하지 않은 첫 번째 방은 1번 방이므로 1로 간다. 1번 방에서 방문하지 않은 첫 번째 방은 4, 그다음 4번 방에서 아직 방문하지 않은 첫 번째 방은 5, 이런 식으로 5번 방에서 3번 방까지 간다. 이때 더는 방문하지 않은 방이 없으면 실을 들고 돌아간다. 5번 방으로 돌아가 이곳에서 아직 방문하지 않은 6번 방을 발견한다. 그래서 6번 방을 방문하고 5번 방으로 돌아간다. 5번 방에는 아직 방문하지 않은 7번 방이 있으므로 7번 방을 방문하고, 다시 5번 방으로 돌아간다. 이제 5번 방은 방문하지 않은 방이 없으므로 4번 방으로 돌아간다. 4번 방에도 방문하지 않은 방이 없으므로 되돌아서 1번 방으로 간 다음, 같은 이유로 0번 방으로 돌아간다. 0번 방에서 아직 방문하지 않은 2번 방을 발견하고, 2번 방을 방문한 후 0번 방으로 돌아간다. 이제 0번 방에 이웃한 1, 2, 3번 방을 모두 방문했으므로 끝났다.

▲ 그림 2-20 깊이 우선 미로 탐색