---
id: wiki-2026-0508-bfs-vs-dfs
title: BFS vs DFS
category: 10_Wiki/Topics
status: verified
canonical_id: self
aliases: [Breadth-First vs Depth-First, 너비 우선 vs 깊이 우선]
duplicate_of: none
source_trust_level: A
confidence_score: 0.95
verification_status: applied
tags: [algorithms, graph, traversal, bfs, dfs, search]
raw_sources: []
last_reinforced: 2026-05-10
github_commit: pending
tech_stack:
  language: python
  framework: none
---

# BFS vs DFS

## 매 한 줄
> **"매 graph traversal 의 두 fundamental order: queue (BFS) vs stack (DFS)"**. 매 1959 Moore 의 BFS, 매 1882 Trémaux 의 DFS-like maze. 매 modern algo 의 building block — 매 shortest path, topological sort, cycle detection 의 base.

## 매 핵심

### 매 BFS
- queue (FIFO) 의 사용 — 매 level-by-level expansion.
- **shortest path** 의 unweighted graph 의 guarantee (edge count 기준).
- 매 시간: O(V + E), 매 공간: O(V) (queue + visited).
- 매 응용: shortest hop, level traversal, bipartite check, web crawl (per-depth limit).

### 매 DFS
- stack (LIFO) / recursion 의 사용 — 매 deep dive first.
- **shortest path** 의 X — 매 tree edge order 의 의 의.
- 매 시간: O(V + E), 매 공간: O(V) (recursion stack / explicit stack).
- 매 응용: cycle detection, topological sort, SCC (Tarjan/Kosaraju), maze solving.

### 매 trade-off
| Aspect | BFS | DFS |
|---|---|---|
| Memory | O(b^d) — wide tree 의 explode | O(b·d) — deep stack |
| Path | shortest (unweighted) | any reachable |
| Implementation | queue + iterative | recursion / explicit stack |
| Backtracking | hard | natural |

### 매 응용 differential
1. **shortest path (unweighted)** → BFS.
2. **shortest path (weighted)** → Dijkstra (BFS의 generalization, 매 priority queue).
3. **topological sort** → DFS (post-order reverse) / Kahn's BFS.
4. **cycle detection** → DFS (back edge) / BFS (in-degree).

## 💻 패턴

### BFS basic
```python
from collections import deque
from typing import Dict, List, Set

def bfs(graph: Dict[int, List[int]], start: int) -> List[int]:
    visited: Set[int] = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    return order
```

### BFS shortest path (unweighted)
```python
def bfs_shortest(graph, start, target):
    queue = deque([(start, [start])])
    visited = {start}
    while queue:
        node, path = queue.popleft()
        if node == target:
            return path
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append((nb, path + [nb]))
    return None  # unreachable
```

### DFS recursive
```python
def dfs(graph, node, visited=None, order=None):
    if visited is None: visited, order = set(), []
    visited.add(node)
    order.append(node)
    for nb in graph[node]:
        if nb not in visited:
            dfs(graph, nb, visited, order)
    return order
```

### DFS iterative (avoids recursion limit)
```python
def dfs_iter(graph, start):
    stack, visited, order = [start], set(), []
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node)
        order.append(node)
        # reverse for same order as recursive
        for nb in reversed(graph[node]):
            if nb not in visited:
                stack.append(nb)
    return order
```

### Topological sort (DFS post-order)
```python
def topo_sort(graph):
    visited, order = set(), []
    def visit(n):
        if n in visited: return
        visited.add(n)
        for nb in graph[n]: visit(nb)
        order.append(n)  # post-order
    for n in graph: visit(n)
    return order[::-1]
```

### Cycle detection (DFS with color)
```python
WHITE, GRAY, BLACK = 0, 1, 2

def has_cycle(graph):
    color = {n: WHITE for n in graph}
    def dfs(n):
        color[n] = GRAY
        for nb in graph[n]:
            if color[nb] == GRAY: return True  # back edge
            if color[nb] == WHITE and dfs(nb): return True
        color[n] = BLACK
        return False
    return any(dfs(n) for n in graph if color[n] == WHITE)
```

## 매 결정 기준
| 상황 | Approach |
|---|---|
| shortest path (unweighted) | BFS |
| shortest path (weighted) | Dijkstra / A* |
| topological sort | DFS post-order / Kahn |
| cycle detection | DFS color |
| memory tight, deep tree | DFS |
| memory ample, wide goals | BFS |
| 매 path enumeration / backtrack | DFS |
| 매 web crawl (depth-limited) | BFS with depth |

**기본값**: shortest path 의 BFS, 매 structural analysis (topo, cycle, SCC) 의 DFS.

## 🔗 Graph
- 부모: [[Graph Theory]]
- 응용: [[Dijkstra's Algorithm]] · [[Topological Sort]]

## 🤖 LLM 활용
**언제**: 매 graph 문제 의 first-cut, 매 grid maze, 매 dependency resolution, 매 social network expansion.
**언제 X**: 매 weighted shortest path (Dijkstra), 매 heuristic 가능 시 (A*), 매 huge graph 의 sampling (random walk).

## ❌ 안티패턴
- **BFS의 memory**: 매 huge branching factor → O(b^d) 의 OOM. 매 IDDFS 의 의 의.
- **DFS recursion limit**: Python 의 default 1000 — 매 large graph 의 stack overflow. 매 iterative 의 의.
- **visited X**: 매 cycle 의 infinite loop.
- **BFS의 path 의 다 저장**: O(V²) memory — 매 parent map 의 의 reconstruct.

## 🧪 검증 / 중복
- Verified (CLRS Ch 22; Sedgewick Algorithms 4th).
- 신뢰도 A.

## 🕓 Changelog
| 날짜 | 변경 |
|---|---|
| 2026-05-08 | Phase 1 |
| 2026-05-10 | Manual cleanup — BFS/DFS comparison with topo sort + cycle detection patterns |