Depth-First Search(DFS): 깊이 우선 탐색의 기초부터 실전까지

DFS는 하나의 경로를 가능한 한 깊게 탐색한 뒤 막다른 곳에서 되돌아와 다른 경로를 시도합니다.

Recursion 또는 명시적인 Stack으로 구현할 수 있습니다.

JavaScript 예제

function dfs(graph, start) {
  const visited = new Set();
  const order = [];

  function visit(node) {
    if (visited.has(node)) return;

    visited.add(node);
    order.push(node);

    for (const next of graph[node] ?? []) {
      visit(next);
    }
  }

  visit(start);

  return order;
}

DFS와 BFS

DFS:

Stack / Recursion
깊이 우선

BFS:

Queue
레벨 우선

무가중 최단 경로는 BFS가 보장하지만 DFS는 보장하지 않습니다.

DFS는 Backtracking, Cycle Detection, Dependency 분석에 자연스럽습니다.

Connected Components

방문하지 않은 정점마다 DFS를 새로 시작하면 각 Connected Component를 찾을 수 있습니다.

Cycle Detection

무방향 그래프에서는 Parent를 추적합니다.

방향 그래프에서는 보통:

unvisited
visiting
finished

상태를 사용합니다.

visiting 상태의 정점으로 돌아가는 간선은 Cycle을 의미합니다.

Topological Sort

모든 Dependency를 처리한 뒤 정점을 결과에 추가하는 Postorder DFS로 DAG의 Topological Sort를 만들 수 있습니다.

Backtracking

많은 Backtracking 문제는 상태 공간 Tree를 DFS로 탐색하며:

선택
재귀
되돌리기

패턴을 사용합니다.

활용

• 파일 시스템
• DOM / AST
• Dependency Graph
• Circular Dependency
• Connected Components
• Maze / Grid
• Network Topology

복잡도

Adjacency List 기준:

시간: O(V + E)
공간: O(V)

정리

DFS는 단순한 순회 알고리즘을 넘어 SCC, Bridge, Articulation Point, Topological Sort 같은 고급 그래프 알고리즘의 기반입니다.