1. 깊이 우선 탐색 그래프 탐색은 하나의 정점을 시작으로 모든 정점을 한 번씩 방문하는 것이다. 깊이 우선 탐색(Depth-First Search)이란 그래프 탐색법의 일종으로, 한 정점에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 전부 탐색하는 방법이다. 주로 모든 노드를 방문해야 할 때 이 방법을 선택하며, 너비 우선 탐색(BFS)보다 간단하나 검색 속도는 느릴 수 있다. 불필요한 경우를 차단하는 등의 처리가 없기 때문에 경우의 수가 줄어들 수는 없다. 때문에 N!의 경우의 수를 가지는 문제는 DFS로 풀 수 없다. 또한 최단 경로를 구하는 문제의 경우 그 해는 최단 경로가 되지 않을 수 있다. 해에 도착하면 탐색을 끝내버리기 때문이다. 트리를 기준으로 보았을 때는 자식 노드의 자식 노드 끝까지 따라가 잎(leaf)를 만날 때까지 깊게 탐색하는 꼴이며, 미로 탐색의 예에서는 한 길로 쭉 가다가 더이상 진행할 수 없을 때 직전의 갈림길로 돌아가 다른