그림 6-29를 보면 현재 정점이 다시 시작 정점으로 돌아왔습니다. 그리고 adj[2]={1, 3}을 보면 시작 정점에 인접한 모든 정점을 방문했다는 것을 알 수 있습니다. 그렇다면 for 문이 종료되면서 함수 실행이 종료되고, 마지막 남은 스택 프레임이 사라지면서 알고리즘이 종료됩니다.

▲ 그림 6-29 DFS 7

이것으로 스택을 기반으로 한 DFS 작동 원리를 살펴보았습니다. 이 장을 마치기 전에 두 가지를 더 고민해 보려고 합니다. 스택 기반의 DFS를 스택 프레임을 이용한 DFS가 아니라 스택 자료 구조와 반복문을 가지고 구현해 볼 수는 없을까 하는 생각이 드는군요. 결론부터 말하자면 구현할 수 있습니다. 코드를 보도록 하죠.