루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법.
이름 그대로 깊이를 우선적으로 탐색한다. 방문 기록을 하는 것이 특징.
이런 식으로 진행되고 base case로는 노드를 방문하여 다음 노드가 없으면 return 하는 식으로 진행된다. 재귀로 구현하는 것이 일반적이다. 물론 이는 문제마다 다르고, 개개인의 논리마다 다르다.
정점의 수 : N, 간선의 수 : E