BFS and DFS

Breadth-First Search (BFS) and Depth-First Search (DFS) are the two fundamental ways to traverse graphs and trees. BFS explores level by level; DFS goes deep before backtracking.

Why It Matters

BFS finds shortest paths in unweighted graphs. DFS detects cycles, does topological sorting, and finds connected components. Nearly every graph problem starts with one of these.

Comparison

Property	BFS	DFS
Data structure	Queue (FIFO)	Stack / recursion (LIFO)
Explores	Level by level	Branch by branch
Shortest path	Yes (unweighted)	No
Memory	O(width of graph)	O(depth of graph)
Use for	Shortest path, level order	Cycle detection, topological sort

BFS

from collections import deque
 
def bfs(graph: dict, start: str) -> list:
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order
 
# Shortest path (unweighted)
def shortest_path(graph: dict, start: str, end: str) -> list:
    queue = deque([(start, [start])])
    visited = {start}
    while queue:
        node, path = queue.popleft()
        if node == end:
            return path
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return []  # no path
 
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': ['E'], 'E': []}
assert shortest_path(graph, 'A', 'E') == ['A', 'B', 'D', 'E']

DFS

# Recursive DFS
def dfs_recursive(graph: dict, start: str, visited: set = None) -> list:
    if visited is None:
        visited = set()
    visited.add(start)
    order = [start]
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            order.extend(dfs_recursive(graph, neighbor, visited))
    return order
 
# Iterative DFS (using explicit stack)
def dfs_iterative(graph: dict, start: str) -> list:
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph.get(node, [])):
            if neighbor not in visited:
                stack.append(neighbor)
    return order
 
# Cycle detection in directed graph
def has_cycle(graph: dict) -> bool:
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
 
    def _dfs(node):
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color.get(neighbor, WHITE) == GRAY:
                return True  # back edge = cycle
            if color.get(neighbor, WHITE) == WHITE and _dfs(neighbor):
                return True
        color[node] = BLACK
        return False
 
    return any(_dfs(node) for node in graph if color[node] == WHITE)

Tree Traversal with BFS/DFS

# Level-order traversal (BFS on a tree)
def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

Related

• Graphs — BFS/DFS operate on graphs
• Trees and Binary Search Trees — tree traversal
• Stacks and Queues — BFS uses queue, DFS uses stack
• Dynamic Programming — shortest path problems on weighted graphs
• Backtracking — DFS with pruning