한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되, 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행
ex)
무방향그래프
0 - 1 - 3 - 7 - 4 - 5- 2- 6 순 방문
0에서 출발 → 1 방문했다면 3과 4로 방문할 수 있다
3을 방문하면 7로 진행할 수 밖에 없다. 그러면 0 - 1 - 3 - 7로 방문
이후 7에서는 아까 1에서 방문할 수 있던 노드였던 4로 진행하고 4에서는 이제 방문할 수 있는 인접 노드가 없다 : 0 - 1 - 3 - 7 - 4
그럼 이제 7에서 방문할 수 있는 노드인 5를 방문
5에서는 2로 진행할 수 있다 : 0 - 1 - 3 - 7 - 4 - 5 - 2
마지막 남은 노드인 6을 방문하며 깊이 우선 탐색을 끝낸다. : 0 - 1 - 3 - 7 - 4 - 5- 2- 6 → 예시를 보면 알겠지만 유일한 방문 순서는 아님
이를 구현하기 위해서는 stack으로 어느 정점에서 DFS를 하고 있는지 기억해 되돌아가야 합니다. 재귀적인 성질을 가집니다.
한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문한 후, 방문한 각 인접 정점을 기준으로 방문한 순서에 따라 또 다시 너비 우선 탐색을 시행한다.
ex)
무방향그래프
0에서 출발
0에서 인접한 노드는 1과 2가 있다. 그럼 0 - 1 - 2 탐색
먼저 방문한 1에 대해 너비 우선 탐색 → 3과 4 방문