DFS (depth-first search) – 깊이-우선 탐색

깊이-우선 탐색은 마지막 선택 점으로 되돌아가기 전에 현재의 경로를 가능한 한 멀리 확장하고, 가장 가까운 대안 경로에 대해 시험하는 그래프 탐색 알고리즘이다. 깊이-우선 탐색은 만약 그래프 내의 순환 고리로 들어가면, 해결책을 찾는데 실패할 수도 있다. 그러나, 이러한 우려는 이미 포함되어 있는 노드로 경로를 확장하지만 않는다면 피할 수 있다. 이 탐색방법은 2진 트리에서의 인오더(inorder) 탐색방법과 비슷하다. 이와 대비되는 개념은 너비-우선 탐색으로서, 서로 비슷한 점이 있지만 깊이-우선 탐색은 큐 대신에 스택을 사용한다는 점이 다르다.