Which to use, BFS or DFS?

Use BFS for shortest path, DFS for exploring all paths. Generally BFS is safer.

BFS uses queue, DFS uses stack?

Yes, BFS uses queue, DFS uses stack (or recursion).

Use for shortest distance, level traversal, finding nearest node.

Use for exploring all paths, backtracking, cycle detection.

BFS and DFS | Graph Traversal Algorithms Complete Guide

2026년 3월 28일 · 22분 읽기 · 수정 2026년 3월 28일 Intermediate Tutorial

이 글의 핵심

Complete guide to BFS and DFS for coding interviews. Master breadth-first search and depth-first search with principles, code examples, and problem-solving patterns.

Introduction

”Two Pillars of Graph Traversal”

BFS and DFS are fundamental graph/tree traversal algorithms. They appear very frequently in coding interviews and must be mastered.

1. BFS (Breadth-First Search)

What is BFS?

BFS visits nodes level by level, starting from nearest. Like ripples spreading outward when a stone is thrown in a pond. Used for finding shortest paths in unweighted graphs.

    1
   / \
  2   3
 / \
4   5
BFS order: 1 → 2 → 3 → 4 → 5 (level by level)

Python Implementation

BFS uses a queue to traverse level by level:

from collections import deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result
# Graph (adjacency list)
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2],
    5: [2]
}
print(bfs(graph, 1))  # [1, 2, 3, 4, 5]

BFS Characteristics:

Traverses level by level (nearest nodes first)
Guarantees shortest path (unweighted graphs)
Uses queue (FIFO)
May use more memory than DFS (wide graphs)

Shortest Path (Distance Calculation)

def bfs_shortest_path(graph, start, end):
    visited = {start: 0}  # node: distance
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        
        if node == end:
            return visited[end]
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited[neighbor] = visited[node] + 1
                queue.append(neighbor)
    
    return -1  # No path
# Test
print(bfs_shortest_path(graph, 1, 4))  # 2 (1→2→4)

2. DFS (Depth-First Search)

What is DFS?

DFS goes as deep as possible in one direction, then backtracks when there’s nowhere to go. Like following one wall in a maze until hitting a dead end, then backtracking.

    1
   / \
  2   3
 / \
4   5
DFS order: 1 → 2 → 4 → 5 → 3 (depth first)

Python Implementation (Recursive)

def dfs_recursive(graph, node, visited, result):
    visited.add(node)
    result.append(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, result)
# Usage
visited = set()
result = []
dfs_recursive(graph, 1, visited, result)
print(result)  # [1, 2, 4, 5, 3]

Recursion Advantages:

Concise and intuitive code
Natural backtracking implementation Recursion Disadvantages:
Stack overflow risk with deep recursion
Python default recursion limit: 1000 (changeable with sys.setrecursionlimit)

Python Implementation (Stack)

Iterative implementation using explicit stack:

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            result.append(node)
            
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return result
print(dfs_iterative(graph, 1))  # [1, 2, 4, 5, 3]

3. BFS vs DFS Comparison

Feature	BFS	DFS
Data Structure	Queue	Stack/Recursion
Traversal Order	Level by level	Depth first
Shortest Path	Yes	No
Memory	More	Less
Implementation	Iterative	Recursive
Time Complexity	O(V+E)	O(V+E)
When to use BFS?

✅ Shortest path
✅ Level traversal
✅ Nearest node When to use DFS?
✅ Explore all paths
✅ Backtracking
✅ Cycle detection

4. Problem Solving

Problem 1: Maze Escape (BFS)

from collections import deque
def maze_escape(maze):
    """
    Find shortest distance from (0,0) to (n-1,m-1)
    1: walkable, 0: wall
    """
    n, m = len(maze), len(maze[0])
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = {(0, 0)}
    
    # Up, down, left, right
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    
    while queue:
        r, c, dist = queue.popleft()
        
        if r == n-1 and c == m-1:
            return dist
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if (0 <= nr < n and 0 <= nc < m and 
                maze[nr][nc] == 1 and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))
    
    return -1
# Test
maze = [
    [1, 0, 1, 1, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 1, 0, 1],
    [1, 1, 1, 0, 1]
]
print(maze_escape(maze))  # 9

Problem 2: Number of Islands (DFS)

def count_islands(grid):
    """
    Count connected regions of 1s
    """
    if not grid:
        return 0
    
    n, m = len(grid), len(grid[0])
    visited = set()
    count = 0
    
    def dfs(r, c):
        if (r < 0 or r >= n or c < 0 or c >= m or
            grid[r][c] == 0 or (r, c) in visited):
            return
        
        visited.add((r, c))
        
        # Explore 4 directions
        dfs(r-1, c)
        dfs(r+1, c)
        dfs(r, c-1)
        dfs(r, c+1)
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1 and (i, j) not in visited:
                dfs(i, j)
                count += 1
    
    return count
# Test
grid = [
    [1, 1, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 1]
]
print(count_islands(grid))  # 3

Problem 3: All Paths (DFS)

def all_paths(graph, start, end):
    """
    Find all paths from start to end
    """
    def dfs(node, path):
        if node == end:
            result.append(path[:])
            return
        
        for neighbor in graph[node]:
            if neighbor not in path:
                path.append(neighbor)
                dfs(neighbor, path)
                path.pop()  # Backtrack
    
    result = []
    dfs(start, [start])
    return result
# Test
graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
print(all_paths(graph, 1, 4))
# [[1, 2, 4], [1, 3, 4]]

5. Practical Tips

Coding Interview Tips

# ✅ Always track visited
# Prevents infinite loops in cycles
# ✅ Choose data structure
# BFS: collections.deque (O(1) popleft)
# DFS: list (O(1) pop) or recursion
# ✅ Grid problems
# Use directions array for 4/8 directions
directions = [(-1,0), (1,0), (0,-1), (0,1)]  # 4-way
# directions = [(-1,-1), (-1,0), (-1,1), (0,-1), 
#               (0,1), (1,-1), (1,0), (1,1)]  # 8-way
# ✅ Level-order processing
# Track level size in BFS
level_size = len(queue)
for _ in range(level_size):
    node = queue.popleft()

Common Patterns

Pattern 1: BFS Template

from collections import deque
def bfs_template(graph, start):
    visited = set([start])
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        
        # Process node
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Pattern 2: DFS Template

def dfs_template(graph, node, visited):
    visited.add(node)
    
    # Process node
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_template(graph, neighbor, visited)

Summary

Key Points

BFS: Uses queue, shortest path, O(V+E)
DFS: Uses stack/recursion, all paths, O(V+E)
Selection: Shortest path → BFS, all paths → DFS
Implementation: BFS with queue, DFS with recursion is simpler

Time Complexity

Both BFS and DFS: O(V + E)

V: number of vertices
E: number of edges

Space Complexity

BFS: O(V) - queue can hold entire level
DFS (recursive): O(h) - recursion stack depth h
DFS (iterative): O(V) - explicit stack

Keywords

BFS, DFS, Breadth-First Search, Depth-First Search, Graph Traversal, Queue, Stack, Recursion, Shortest Path, Backtracking, Coding Interview, Algorithm

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Complete guide to BFS and DFS for coding interviews. Master breadth-first search and depth-first search with principles,… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

스택과 큐 | 코딩 테스트 필수 자료구조 완벽 정리
그래프 자료구조 | 인접 리스트, 인접 행렬, 탐색 완벽 정리
[Graph Data Structure | Adjacency List· Matrix](/en/blog/algorithm-series-05-graph/

이 글에서 다루는 키워드 (관련 검색어)

Algorithm, BFS, DFS, Graph, Search, Coding Interview, Tree 등으로 검색하시면 이 글이 도움이 됩니다.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

Keyboard Shortcuts

BFS and DFS | Graph Traversal Algorithms Complete Guide

이 글의 핵심

Introduction

”Two Pillars of Graph Traversal”

BFS and DFS are fundamental graph/tree traversal algorithms. They appear very frequently in coding interviews and must be mastered.

1. BFS (Breadth-First Search)

What is BFS?

Python Implementation

Shortest Path (Distance Calculation)

2. DFS (Depth-First Search)

What is DFS?

Python Implementation (Recursive)

Python Implementation (Stack)

3. BFS vs DFS Comparison

4. Problem Solving

Problem 1: Maze Escape (BFS)

Problem 2: Number of Islands (DFS)

Problem 3: All Paths (DFS)

5. Practical Tips

Coding Interview Tips

Common Patterns

Summary

Key Points

Time Complexity

Space Complexity

Recommended Problems

Beginner

Intermediate

Advanced

Keywords

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

Q. 선행으로 읽으면 좋은 글은?

Q. 더 깊이 공부하려면?

같이 보면 좋은 글 (내부 링크)

이 글에서 다루는 키워드 (관련 검색어)

이 글이 도움이 되셨나요?

Keyboard Shortcuts

이 글의 핵심

Introduction

”Two Pillars of Graph Traversal”

BFS and DFS are fundamental graph/tree traversal algorithms. They appear very frequently in coding interviews and must be mastered.

1. BFS (Breadth-First Search)

What is BFS?

Python Implementation

Shortest Path (Distance Calculation)

2. DFS (Depth-First Search)

What is DFS?

Python Implementation (Recursive)

Python Implementation (Stack)

3. BFS vs DFS Comparison

4. Problem Solving

Problem 1: Maze Escape (BFS)

Problem 2: Number of Islands (DFS)

Problem 3: All Paths (DFS)

5. Practical Tips

Coding Interview Tips

Common Patterns

Summary

Key Points

Time Complexity

Space Complexity

Recommended Problems

Beginner

Intermediate

Advanced

Related Posts

Keywords

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

Q. 선행으로 읽으면 좋은 글은?

Q. 더 깊이 공부하려면?

같이 보면 좋은 글 (내부 링크)

이 글에서 다루는 키워드 (관련 검색어)

이 글이 도움이 되셨나요?