깊이 우선 탐색
개요
깊이 우선 탐색(Depth-first search, DFS)은 아직 방문하지 않은 이웃을 따라 한 갈래를 끝까지 파고들고, 더 나아갈 곳이 없으면 직전 갈림길로 되돌아와(backtracking) 다음 갈래를 잇는 그래프 탐색이다. 폴더 트리에서 하위 폴더를 끝까지 열어 본 뒤 상위 폴더로 올라와 옆 폴더를 여는 과정과 같으며, 각 갈림길에서 어디까지 읽었는지를 기억해야 되돌아왔을 때 이어서 탐색할 수 있다.
연혁
막다른 길에서 직전 교차로로 되돌아오는 탐색 규칙은 19세기 Charles Pierre Trémaux의 미로 해법으로 거슬러 올라가며, Édouard Lucas가 1882년 *Récréations Mathématiques*에서 이를 소개했다.1 컴퓨터 알고리즘으로는 John Hopcroft와 Robert Tarjan이 1971–1972년 연구를 통해 깊이 우선 탐색이 만드는 신장 트리(DFS palm tree)와 역방향 간선의 성질을 정식화했고, Tarjan의 1972년 논문 「Depth-First Search and Linear Graph Algorithms」에서 강연결 요소(SCC)와 이중연결 요소를 모두 선형 시간에 구하는 해법으로 이어졌다.2
명시적 스택 프레임과 괄호 정리
재귀 함수로 DFS를 작성하면 언어 런타임의 호출 스택이 이전 정점과 다음 읽을 이웃 위치를 기억하지만, 깊이가 수만 단계인 긴 경로 그래프에서는 호출 스택 한계를 넘어 RangeError: Maximum call stack size exceeded가 발생할 수 있다. 아래 구현은 각 정점의 재개 인덱스 next를 힙 배열의 프레임 { vertex, next }에 직접 담아 호출 스택 오버플로 없이 재귀 DFS와 완전히 동일한 탐색 순서를 만든다.
흔히 비재귀 DFS라고 소개되는 코드 중에는 정점을 꺼내며 이웃 전체를 한꺼번에 스택에 넣는 변형이 있다. 그러나 그 방식은 이웃을 역순으로 처리할 뿐 아니라 아직 탐색하지 않은 정점 사본이 스택에 중복으로 쌓여 공간이 까지 늘어난다. 반면 프레임에 next 인덱스를 두면 스택에는 언제나 출발점에서 현재 정점까지 이어지는 활성 조상 경로만 남는다. 정점 를 처음 발견한 시각을 , 모든 이웃을 마치고 스택에서 빠지는 시각을 라 하면 임의의 두 정점 구간은 서로소이거나 한쪽이 다른 쪽에 완전히 포함되는 괄호 정리(parenthesis theorem)를 만족한다.
실행 예제
너비 우선 탐색 예제와 똑같은 방향 그래프에서 탐색 순서가 어떻게 달라지는지 확인해 보자. A에서 B로 들어간 뒤 C로 가지 않고 B의 자식 D까지 먼저 내려간다. 방문 배열 seen이 이미 발견한 정점으로 다시 진입하는 순환을 차단한다.
function depthFirst(graph: readonly (readonly number[])[], start: number): number[] {
const seen = new Array<boolean>(graph.length).fill(false);
const order = [start];
// 각 정점에서 다음에 읽을 이웃 인덱스(next)를 함께 저장해 재귀 복귀 지점을 모사한다.
const stack = [{ vertex: start, next: 0 }];
seen[start] = true;
while (stack.length > 0) {
const frame = stack[stack.length - 1]!;
const neighbors = graph[frame.vertex]!;
if (frame.next === neighbors.length) {
stack.pop();
continue;
}
const to = neighbors[frame.next++]!;
if (seen[to]) continue;
seen[to] = true;
order.push(to);
stack.push({ vertex: to, next: 0 });
}
return order;
}
const names = ['A', 'B', 'C', 'D', 'E'];
const graph = [[1, 2], [3], [3, 4], [], []];
console.log(depthFirst(graph, 0).map(index => names[index]).join(','));실행 결과:
A,B,D,C,EB의 갈래를 끝내고 A로 복귀해 C를 방문할 때, D는 이미 seen[3] === true이므로 건너뛰고 E로 나아간다. 프레임에 next를 저장했기 때문에 자식 탐색에서 돌아왔을 때 부모의 인접 리스트를 처음부터 다시 훑지 않고 직전 위치 다음부터 이어 읽는다.
C++ 예제
C++에서도 운영체제 스레드 기본 스택 크기(보통 1~8 MiB)는 깊이가 수십만인 경로 그래프에서 재귀 호출 시 스택 오버플로를 일으킬 수 있다. std::vector<Frame>에 정점 번호와 이웃 인덱스 next를 함께 보관하되, stack.push_back이 재할당을 일으킬 수 있으므로 매 반복마다 stack.back() 참조를 새로 읽는다.
#include <cstddef>
#include <iostream>
#include <vector>
struct Frame {
int vertex;
std::size_t next;
};
std::vector<int> depthFirst(const std::vector<std::vector<int>>& graph, int start) {
std::vector<bool> seen(graph.size(), false);
std::vector<int> order{start};
// 각 정점에서 다음에 읽을 이웃 인덱스(next)를 저장해 재귀 복귀 지점을 모사한다.
std::vector<Frame> stack{{start, 0}};
seen[start] = true;
while (!stack.empty()) {
Frame& frame = stack.back();
const auto& neighbors = graph[frame.vertex];
if (frame.next == neighbors.size()) {
stack.pop_back();
continue;
}
int to = neighbors[frame.next++];
if (seen[to]) continue;
seen[to] = true;
order.push_back(to);
stack.push_back({to, 0});
}
return order;
}
int main() {
const char names[] = {'A', 'B', 'C', 'D', 'E'};
const std::vector<std::vector<int>> graph{{1, 2}, {3}, {3, 4}, {}, {}};
const auto order = depthFirst(graph, 0);
for (std::size_t i = 0; i < order.size(); ++i) {
if (i > 0) std::cout << ',';
std::cout << names[order[i]];
}
std::cout << '\n';
return 0;
}실행 결과:
A,B,D,C,E비용과 적용 범위
정점 수 , 간선 수 에 대해 각 정점은 스택에 최대 한 번 들어가고 각 정점의 next 포인터는 그 정점의 진출 차수만큼만 증가하므로 시간 복잡도는 다. 스택에는 현재 활성 경로의 정점만 들어 있으므로 보조 공간 복잡도는 로 유지된다.
DFS는 최단 간선 거리를 구해주지는 않지만, 완료 시각()의 역순으로 위상 정렬(topological sort)을 구하거나, 현재 스택에 머물고 있는 조상 정점으로 향하는 역방향 간선(back edge)을 감지해 방향 그래프의 순환(cycle) 여부를 판별하고, 단절점·강연결 요소를 선형 시간에 찾는 알고리즘의 토대가 된다.