dfs 함수가 제대로 동작하는지 테스트해 봅시다. 함수 중간에 있는 print를 통해 버텍스들을 어떤 순서로 방문했는지 확인할 수 있습니다. 방문 기록을 저장하는 visited는 세트이기 때문에 방문한 순서대로 버텍스가 정렬되어 있지 않습니다.
[in :]
dfs(graph, 'Amin')
[out:]
Amin
Mike
Wasim
Imran
Faras
Nick
{'Imran', 'Wasim', 'Faras', 'Amin', 'Mike', 'Nick'}
DFS 알고리즘의 작동 방식은 다음과 같습니다.
• 그래프의 맨 위 버텍스인 Amin부터 시작합니다.
• 레벨 2에 있는 Wasim을 방문합니다. Wasim에 연결된 레벨 3 버텍스인 Imran, 레벨 4 버텍스인 Faras를 방문하고 경로의 끝에 도달합니다.
• 경로를 시작했던 Amin 버텍스로 되돌아옵니다. 그리고 아직 방문하지 않은 레벨 2 버텍스인 Nick과 Mike를 차례로 방문합니다.