코드 6-8은 dfs를 재귀 함수로 구현한 것입니다. 코드에서 __dfs_recursion()과 dfs()를 보고 혼란스러울 수 있지만 dfs에서 __dfs_recursion을 호출하기 전에 visited 배열을 초기화하고자 dfs를 만든 것뿐입니다. 중요한 메서드는 __dfs_recursion입니다. __dfs_recursion을 보면 매개변수로 v를 받습니다. 그 후 먼저 방문을 하고 visited[v]를 True로 만들지요. 그러고 나서 adj[v]를 구합니다. adj[v]를 순회하며 방문하지 않은 정점을 방문할 때는 그 정점을 인수로 전달하며 __dfs_recursion을 호출합니다.

코드는 간단한데 이해하기가 조금 어렵군요. 그림으로 살펴보겠습니다. 그림 6-22를 보면 BFS와 비교되는 DFS 특징을 알 수 있습니다.

▲ 그림 6-22 DFS 특징

BFS는 시작 정점을 기준으로 인접한 모든 노드를 차례로 방문하며 마치 퍼져 나가듯이 방문했습니다. 하지만 DFS는 이와 다르게 시작 정점에서 한 방향을 정하고 그 분기로 쭉 따라간 후 더 이상 갈 곳이 없어지면 다시 시작 정점으로 돌아와 가보지 않은 방향으로 쭉 따라가는 특성이 있습니다. 그래서 이름도 깊이 우선 탐색입니다. 그림을 보면 시작 정점 3에서 시작하여 정점 0 쪽으로 쭉 따라간 후 정점 1에서 더 이상 갈 곳이 없어지면 다시 시작 정점으로 돌아옵니다. 그다음 다시 정점 4 방향으로 쭉 따라 이동하면서 방문한 후 다시 정점 3으로 돌아와 더 이상 갈 곳이 없어지면 종료되지요. 여기서 중요한 점은 반드시 시작 정점으로 돌아온 후 더 이상 갈 곳이 없어야만 실행이 종료된다는 것입니다.