그래프에서 한 갈래를 갈 수 있는 데까지 깊이 들어갔다가, 막히면 되돌아와(백트래킹, Backtracking) 다른 갈래로 가는 탐색. 방문한 정점은 기록해 다시 가지 않는다.
function dfs(graph: Record<string, string[]>, start: string) {
const visited = new Set<string>()
const order: string[] = []
const visit = (v: string) => {
visited.add(v)
order.push(v)
for (const next of graph[v]) if (!visited.has(next)) visit(next)
}
visit(start)
return order
}- 재귀로 쓰면 짧다. 그래프가 깊으면 콜 스택이 넘칠 수 있어, 명시적 스택에 넣고 빼는 반복문으로 바꿀 수 있다. 두 방식은 이웃을 넣는 순서 때문에 방문 순서가 다를 수 있다
- 시간
O(V + E), 메모리는 경로 깊이만큼 - 쓰임: 경로가 있는지, 연결된 덩어리가 몇 개인지, 순환이 있는지 확인. 위상 정렬(Topological Sort), 미로 풀이, 퍼즐의 모든 경우 탐색(백트래킹)
최단 경로(간선 수 기준)를 찾을 때는 DFS가 아니라 너비 우선 탐색 (BFS)를 쓴다. 트리에서의 깊이 우선 순회(전위·중위·후위)는 트리 순회, 그래프 표현은 그래프.