깊이 우선 탐색 (Depth-First Search)

깊이 우선 탐색 (DFS)

• 루트 노드 (혹은 임의의 다른 노드)에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 깊게 (depp) 탐색
• 모든 노드를 방문 하고자 하는 경우에 사용
• 단순 검색 속도는 BFS에 비해 느림
• 자기 자신을 호출하는 순환 알고리즘의 형태
• 전위 순회 (Pre-Order Traversals)를 포함한 다른 형태의 트리 순환은 모두 DFS의 한 종류
• 그래프 탐색의 경우 어떤 노드를 방문했는지 방문 여부를 반드시 검사해야 함 (안하면 무한루프 빠질 위험 있음)

깊이 우선 탐색 (DFS) 과정

1. a 노드(시작 노드)를 방문 (방문 여부 체크)
2. a와 인접한 노드 차례로 순회
   • 인접한 노드 없으면 종료
3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 함
   • b를 시작 정점으로 DFS 다시 시작
4. b의 분기(branch)를 완벽하게 탐색했다면 다시 a에 인접한 정점들 중 아직 방문 안한 정점 찾음
   • b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드 방문 가능
   • 방문이 안된 정점을 시작 정점으로 DFS 다시 시작