[2026] BFS and DFS | Graph Traversal Algorithms Complete Guide

· 22분 읽기 · 수정 Intermediate Tutorial
[2026] BFS and DFS | Graph Traversal Algorithms Complete Guide

이 글의 핵심

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.

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. 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

    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: 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)

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. 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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

Python Implementation (Recursive)

아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

FeatureBFSDFS
Data StructureQueueStack/Recursion
Traversal OrderLevel by levelDepth first
Shortest PathYesNo
MemoryMoreLess
ImplementationIterativeRecursive
Time ComplexityO(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)

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ✅ 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 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

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

  1. BFS: Uses queue, shortest path, O(V+E)
  2. DFS: Uses stack/recursion, all paths, O(V+E)
  3. Selection: Shortest path → BFS, all paths → DFS
  4. 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

Beginner

  • LeetCode 104: Maximum Depth of Binary Tree
  • LeetCode 111: Minimum Depth of Binary Tree
  • LeetCode 733: Flood Fill

Intermediate

  • LeetCode 200: Number of Islands
  • LeetCode 207: Course Schedule
  • LeetCode 127: Word Ladder

Advanced

  • LeetCode 301: Remove Invalid Parentheses
  • LeetCode 126: Word Ladder II
  • LeetCode 417: Pacific Atlantic Water Flow

Keywords

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

... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3