Depth-first Search
Depth-first search (DFS) 는 트리 (Tree), 그래프 (Graph) 를 탐색하는 알고리즘이다. 쉽게 얘기하면, root에서 출발하여 (graph 에서는 어떤 노드를 선택해서) backtracking 하기 전까지 각 branch에서 가능한 멀리까지 탐색한다.
DFS 는 탐색 트리의 최초의 자식노드 (child node) 를 확장하여 목표상태 (goal state) 가 발견될 때까지 더 깊이 (deeper and deeper) 확장하는 무정보 탐색 (Uninformed or Blind Search) 이다. 만일 자식노드를 갖지 않은 노드에 이르면 backtrack 하여 다음 노드에서 출발한다. 새로이 확장된 모든 노드들은 확장을 위해 LIFO queue (stack) 에 더해진다.
DFS 의 공간복잡도 (space complexity) 는 너비우선 탐색 (Breadth-first Search) 보다 훨씬 더 낮다. 또한 그럴 듯한 가지 (likely-looking branch) 를 선택하는 휴리스틱 (Heuristic) 방법에 더 쉽게 적응한다.
memory 에 완전히 담을 수 없는 큰 규모의 그래프를 탐색할 때, DFS 는 탐색트리에서 경로의 길이가 무한할 때와 같은 non-termination 이 발생한다. "이미 보았던 노드들을 기억하는" 간단한 해법은 메모리가 불충분할 때는 작동하지 않게된다. 이것은 트리의 깊이의 한계를 증가시켜서 해결할 수 있는데, 소위 iterative deepening depth-first search 라고 불리운다.
위의 그래프에서 DFS 는 A에서 출발하고, 왼쪽 edge 가 오른쪽 edge 보다 먼저 선택되고, 이전에 방문한 노드들을 기억하고, 방문한 노드들을 반복하지 않는다 (위의 그래프는 작은 그래프이기 때문에) 고 하면, 다음의 순서대로 탐색이 이루어진다.
A, B, D, F, E, C, G.
만일 이전에 방문한 노드들을 기억하지 않고, 이전 단락에서 다른 조건들이 주어졌다면, 탐색은 A, B, D, F, E, A, B, D, F, E, 등등으로 A, B, F, E cycle 에 잡혀서 영원히 수행되고, 결코 C 나 G 에 도달하지 못할 것이다.
Iterative deepening 은 이러한 loop를 방해하며, 위에서와 마찬가지로 오른쪽에서 왼쪽으로 탐색이 진행된다고 하면, 다음 깊이 (depth) 에 있는 다음 노드들에 이를 것이다.
(기존의 DFS 와는 달리 iterative deepening 은 지금 C 가 보이는 것을 주목하라)
(여전히 C 가 보이지만 뒤로 밀린 것을 알 수 있다. 다른 경로를 통해 E 가 보이는 것을 주목하라, 그리고 F 가 두 번 반복한다)
위의 그래프에서 더 많은 깊이 (depth) 가 더해짐에 따라, 알고리즘이 끝나기 전에는 두 개의 cycle "ABFE" 와 "AEFB" 은 더 길어질 뿐이며 또다른 가지를 탐색한다 (Wikipedia : Depth-first Search).
Pseudocode
DFS(Start,Goal)
push(Stack,Start)
while(notEmpty(Stack))
Node <- Pop(Stack)
if (Node == Goal)
return Node
forall Child <- Expand(Node)
push(Stack, Child)
Site :
Graph Algorithms : DFS java code
C++ Boost Graph Library: Depth-First Search
paper :
깊이우선 또는 되추적 탐색 (Depth-First or Backtracking Search) : Nils J.Nilsson
깊이우선 탐색 (Depth-first search) : Dan W. Patterson
변형된 점증 깊이우선 탐색방법을 사용한 로봇 계획시스템 (A Robot Planning System Based on a Modified DFID Search Method) : 임재걸, 한국정보처리학회, 1995
분산 깊이우선 탐색 프로토콜의 복잡도 개선을 위한 연구 (Improvement on The Complexity of Distributed Depth First Search Protocol) : 최종원, 한국정보처리학회, 1996