코드 6-9는 스택 자료 구조와 반복문을 이용해서 dfs를 구현한 것입니다. 몇 가지만 짚고 넘어가겠습니다. 먼저 while 문 내에서 dfs처럼 큐에서 정점을 바로 가져오지 않고 peek() 메서드로 읽어만 옵니다. 그럼 아직 현재 정점이 스택에 남아 있게 되지요. 이 점이 중요합니다.

그 후 현재 정점 v에 대해 adj[v]를 구해 와 for 문을 돌며 방문하지 않은 정점에 대해 방문과 방문 체크를 합니다. 이때 방문하지 않은 정점을 만나 방문을 한다면 is_visited 변수를 True로 만들어 주죠. 방문하지 않은 정점을 발견하면 현재 정점이 방문하지 않은 정점으로 이동하므로 for 문을 빠져나가 다시 while 문의 처음부터 실행하는 것입니다.

이때 for 문을 빠져나올 때 두 가지 경우가 있겠지요. 먼저 is_visited가 True면 이는 방문하지 않은 정점을 발견하여 이동한 경우입니다. 이때는 스택에 이전 정점 위에 이번에 이동한 정점이 쌓여 있을 것입니다. 이렇게 해야 다음에 모든 정점을 방문한 시점에서 pop()으로 현재 정점을 제거하고 이전 정점으로 이동할 수 있으니까요. is_visited가 False라면 이는 adj[v]의 모든 노드를 방문한 상태라는 것입니다. 이때는 이전 정점으로 이동해야 하므로 스택에서 현재 정점을 pop해야 합니다. 그럼 이전 정점으로 돌아갈 수 있습니다.

두 번째로 그래프가 연결되어 있지 않고 여러 개의 연결 요소로 나뉘어 있다면 어떨까요? 그렇다면 지금의 dfs로는 모든 정점을 방문하지 못하고 시작 정점에 연결된 요소의 정점들만 방문할 것입니다. 이를 해결하는 dfs_all 메서드를 만들어 봅시다.