DFS

Depth First Search. 흔히 줄여서 DFS로 쓴다. 한국어 표기는 깊이 우선 탐색.
거의 항상 넓이우선탐색(BFS; Breadth First Search)과 비교되어 나온다.

트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.[1]

갈림길이 나타날 때마다 '다른 길이 있다'는 정보만 기록하면서 자신이 지나간 길을 지워나간다. 그러다 막다른 곳에 도달하면 직전 갈림길까지 돌아가면서 '이 길은 아님'이라는 표식을 남긴다. 그렇게 갈림길을 순차적으로 탐색해 나가다 목적지를 발견하면 그대로 해답을 내고 종료.

단순 검색 속도 자체는 BFS에 비해서 느리다. 하지만 검색이 아닌 트래버스(traverse)를 할 경우는 많이 쓰인다. DFS는 특히 리프 노드에만 데이터를 저장하는 정렬 트리 구조에서 항상 순서대로 데이터를 방문한다는 장점이 있다. 백트래킹에 사용되는 이유도 공통 상위를 가지는 아래 리프 노드들을 한방에 잘라 내 버리는게 가능하기 때문이다.

자동 미로 생성에 많이 사용되는 알고리즘이기도 하다. 방향은 무작위로 해서 계속 뚫다가 막혀서 못 뚫으면 뚫을 수 있는 곳이 발견될 때까지 되돌아가서 다시 뚫고, 또 막히면 되돌아가고 이런 식으로 무한히 반복하다 보면 생긴다. 게다가 이 방식으로 미로를 만들면 빠져나가는 경로 또한 단 하나만 생긴다. 직접 보고 싶다면 이 동영상을 보자.

DFS를 잘만 이용하면 방향 있는 그래프에서 사이클(cycle)이 있는지 판단하는 것도 가능하다. 즉 어떤 한 임의의 노드에서 길을 따라 가보면 자기 자신으로 돌아올 수 있는 경로가 있는지 확인할 수 있다.

한 정점을 두번 이상 방문하지 않는 연결그래프에서 DFS트리라는 유향트리 구조가 만들어진다.

DFS 트리를 사용하면 unrooted tree를 rooted tree로 만들 수 있다. 이 경우에는 Tree edge이외의 간선이 존재하지 않게 된다.