BFS vs DFS : A Decision Guide

The shared skeleton

Both algorithms perform the same conceptual operation: starting from a source, explore every reachable node exactly once, in a particular order. The difference is purely the data structure used to manage the frontier.

# BFS - queue
from collections import deque

def bfs(graph, source):
    visited = {source}
    q = deque([source])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                q.append(v)
    return order

# DFS - recursion (stack implicit in the call stack)
def dfs(graph, source):
    visited = set()
    order = []
    def visit(u):
        if u in visited: return
        visited.add(u)
        order.append(u)
        for v in graph[u]:
            visit(v)
    visit(source)
    return order

For a graph of V nodes and E edges, both run in O(V + E): each node is visited once, each edge examined once. Memory: BFS up to O(V) for the queue (in the worst case, the whole graph); DFS up to O(V) for the call stack. Same asymptotics; very different traversal orders.

When BFS

Shortest path on an unweighted graph

BFS visits nodes in order of distance from the source. So when the answer is "the smallest number of edges from A to B", BFS gives it directly. Modify the algorithm to track distances:

def shortest_path(graph, source):
    dist = {source: 0}
    q = deque([source])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

The first time we discover a node, the distance recorded is the shortest in number of edges. This is the canonical reason BFS exists.

Shortest path with edge weights: Dijkstra (BFS with a priority queue)

Replace the FIFO queue with a min-priority-queue keyed on distance. Pop the smallest, relax outgoing edges. The structure is BFS; the data structure swap raises complexity to O((V + E) log V). See the Graphs module for the full Dijkstra walkthrough.

Multi-source spreading (rotting oranges, flood fill, propagation problems)

Initialise the queue with multiple sources. The algorithm naturally simulates simultaneous expansion, where each "level" represents one time step. Used for "minimum time for X to spread everywhere" and "find the cell furthest from any source" problems.

Bidirectional BFS

For shortest-path queries between two specific nodes, BFS from both ends and meet in the middle. Cuts the explored space from O(b^d) to O(2 × b^(d/2)), an exponential improvement on graphs with high branching factor. Used in word-ladder problems.

When DFS

Cycle detection

DFS naturally detects cycles by tracking nodes "on the recursion stack". When DFS encounters a neighbour that's still being explored (on the stack, not just visited), there's a back edge, and that means a cycle.

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {u: WHITE for u in graph}
    def dfs(u):
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY: return True            # back edge
            if color[v] == WHITE and dfs(v): return True
        color[u] = BLACK
        return False
    return any(dfs(u) for u in graph if color[u] == WHITE)

The three-colour invariant is the textbook framing. WHITE = unvisited, GRAY = in current DFS path, BLACK = fully explored. Encountering a GRAY neighbour means we've looped back to a node still on the recursion stack: a cycle.

Topological sort (DAG only)

Run DFS; record nodes in post-order (when DFS finishes with them, not when it discovers them). Reverse the post-order and you get a valid topological order. The intuition: a node is finished only after all its descendants are; reversing puts all-descendants-first, parent-second order, which is exactly the topological direction.

def topo_sort(graph):
    visited = set()
    order = []
    def dfs(u):
        if u in visited: return
        visited.add(u)
        for v in graph[u]:
            dfs(v)
        order.append(u)                                  # post-order
    for u in graph:
        dfs(u)
    return order[::-1]                                   # reverse

Kahn's algorithm (the BFS variant of topological sort using in-degree counts) also works and is easier to extend with cycle detection inline. Both run in O(V + E).

Connected components / island counting

Iterate every node; when you find an unvisited one, run DFS (or BFS) from it, marking everything reachable as visited. Each DFS launch is one component. Counting them gives the answer.

def count_components(graph):
    visited = set()
    count = 0
    def dfs(u):
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                dfs(v)
    for u in graph:
        if u not in visited:
            visited.add(u)
            dfs(u)
            count += 1
    return count

Backtracking

Backtracking is DFS with explicit "try, then undo" semantics: N-queens, sudoku, generate all permutations. The DFS visits a tree of partial solutions; the "undo" before returning restores state for the next candidate.

Grid problems: usually either works

For "find connected regions on a 2D grid" (number of islands, max area of island, surrounded regions), both DFS and BFS work. The choice matters when:

• The grid is huge and recursion would overflow. BFS with explicit queue avoids stack issues.
• You need shortest distances (rotting oranges). BFS only.
• The boundary expansion order matters (Pacific Atlantic water flow). Multi-source BFS from each shore; DFS works too but is less natural.

Memory profile

Both are O(V) worst case but with different shapes:

• BFS: queue can hold an entire "layer" of the BFS tree. On graphs with high branching factor and shallow targets, the queue can balloon to most of the graph.
• DFS: stack holds the current path from source. On graphs with long paths but low branching, DFS uses less memory than BFS, but on a deep linear structure, recursion can overflow.

For very deep paths (chain graphs of 10⁶ nodes), iterative DFS with an explicit stack avoids the recursion limit; recursive DFS won't work in Python without increasing sys.setrecursionlimit.

Decision guide

Where beginners go wrong

• Marking visited too late. In BFS, mark when enqueueing, not when dequeueing; otherwise you can enqueue the same node multiple times. The cost is O(V × degree) instead of O(V + E).
• Using DFS for shortest path. DFS finds some path, not the shortest. BFS finds shortest in number of edges; Dijkstra in weight.
• Forgetting cycle detection requires the three-colour invariant. "Visited or not" isn't enough. You need to distinguish "currently being explored" from "fully done".
• Recursive DFS on graphs with long paths. Stack overflow in Python past ~1000 nodes. Convert to iterative DFS with an explicit stack.
• Confusing Kahn's BFS topo-sort with regular BFS. Kahn's tracks in-degree; regular BFS tracks distance. The data structures look similar; the semantics differ.

What to read next

The Graphs module covers Dijkstra and the broader algorithm family. The Trees module presents the same machinery applied to acyclic structures. The blog essay Recognise the Shape shows how to spot when a problem is secretly a graph problem.