BFS vs DFS in Java — Complexity, Memory, Use Cases

BFS vs DFS — the difference

BFS (Breadth-First Search)

• Queue (FIFO)
• Level by level
• Finds shortest path in unweighted graph

DFS (Depth-First Search)

• Stack (LIFO) or recursion
• As deep as possible, then backtrack
• Path enumeration, cycle detection

Both O(V + E) for graphs, O(n) for trees.

Memory

• BFS: O(W) max width
• DFS: O(H) max depth
• Wide tree: DFS wins (O(log n) vs O(n))
• Skewed tree: BFS wins (O(1) per level vs O(n) recursion)

When to use BFS

1. Shortest path in unweighted graph

• Guarantees minimum hops
• Track distance and parent

2. Minimum steps to reach target

• Word ladder, transformations

3. Level-order traversal

• Tree level by level

4. All nodes within distance K

• Stop at depth K

5. Bipartite check

• Alternate colors level by level

6. Web crawler within N hops

When to use DFS

1. Path enumeration

• Find any or all paths
• Backtracking-friendly

2. Cycle detection

• Directed: 3-color (WHITE/GRAY/BLACK)
• Back edge to GRAY = cycle

3. Topological sort

• Postorder, then reverse
• Or Kahn's BFS

4. Connected components

• Each unvisited start = new component

5. Strongly connected components

• Tarjan's, Kosaraju's

6. Maze / N-queens / Sudoku

• Classic backtracking

7. Tree problems

• Subtree sums, heights, LCA

Don't use DFS for shortest path

• DFS finds A path, not THE shortest
• Even on unweighted graphs

For weighted shortest path

• Dijkstra (BFS + priority queue) for non-negative
• Bellman-Ford for negative weights
• Floyd-Warshall for all-pairs (small V)

Implementations — Java

BFS tree

Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
    TreeNode n = q.poll();
    visit(n);
    if (n.left != null) q.offer(n.left);
    if (n.right != null) q.offer(n.right);
}

BFS graph (with cycle protection)

Set<Integer> visited = new HashSet<>();
Queue<Integer> q = new ArrayDeque<>();
q.offer(start);
visited.add(start);
while (!q.isEmpty()) {
    int node = q.poll();
    for (int next : adj.get(node)) {
        if (visited.add(next)) q.offer(next);
    }
}

DFS recursive

void dfs(int node, Set<Integer> visited) {
    if (!visited.add(node)) return;
    visit(node);
    for (int next : adj.get(node)) dfs(next, visited);
}

DFS iterative

Deque<Integer> stack = new ArrayDeque<>();
stack.push(start);
while (!stack.isEmpty()) {
    int node = stack.pop();
    if (!visited.add(node)) continue;
    visit(node);
    for (int next : adj.get(node)) stack.push(next);
}

Always use ArrayDeque

• Faster than LinkedList for queue
• Faster than legacy Stack class

Advanced variants

Bidirectional BFS

• Search from both source and target
• Meet in middle
• O(b^(d/2)) instead of O(b^d)
• Huge speedup for large graphs

Iterative Deepening DFS (IDDFS)

• DFS with depth limit, repeated
• BFS-like behavior (finds shortest)
• DFS memory (O(d))
• Use for huge search spaces (chess)

0-1 BFS

• For edges weighted 0 or 1
• Deque: push 0 to front, 1 to back
• O(V + E)

*A* search*

• BFS + heuristic
• Optimal if heuristic admissible
• Pathfinding in games, robotics

Dijkstra

• BFS + priority queue
• Non-negative weighted shortest path
• O((V + E) log V)

Multi-source BFS

• Start from multiple sources
• 'Closest of any source' problems

Common bugs

1. Reversed data structures

• BFS uses queue, DFS uses stack
• Mixing them → wrong order

2. Forgetting visited set

• Graph traversal without visited → infinite loop on cycles

3. DFS for shortest path

• DFS finds a path, not the shortest
• Use BFS

4. Stack overflow

• Deep recursion in DFS
• Use iterative for unknown-depth graphs

5. OOM on wide BFS

• Last level can hold n/2 nodes
• Use bidirectional or limit

6. Wrong cycle detection

• Undirected: simple visited works
• Directed: need 3-color (back edge to GRAY)

For interviews

• BFS shortest path vs DFS path enumeration
• Mention 3-color cycle detection
• Topological sort: DFS postorder reversed
• ArrayDeque for both
• Bidirectional BFS for large-graph shortest path
• Dijkstra as 'BFS + priority queue' for weights

Recommendation: Use BFS (queue, FIFO) for shortest path in unweighted graphs, level-order traversal, finding all nodes within distance K, bipartite checks, and any 'find shortest / minimum steps' problem — the level-by-level expansion guarantees that the first time you reach the target, it's via the shortest path. Use DFS (stack or recursion, LIFO) for path enumeration, cycle detection (3-color WHITE/GRAY/BLACK — back edge to GRAY = cycle), topological sort (reverse postorder of DAG), connected components, strongly connected components (Tarjan/Kosaraju), and backtracking problems (mazes, N-queens, Sudoku). Both are O(V + E) time, but memory differs: BFS is O(W) max width (can be O(n) for wide trees), DFS is O(H) max height (O(log n) balanced, O(n) skewed). In Java, always use `ArrayDeque` for both queue and stack — faster than LinkedList and the legacy Stack class. Don't use DFS for shortest path — it finds a path, not the shortest. For weighted shortest path, use Dijkstra's algorithm (BFS with priority queue, non-negative weights), Bellman-Ford (negative weights, detects negative cycles), or Floyd-Warshall (all-pairs, small V). For huge graph shortest path, consider bidirectional BFS (meets in middle, O(b^(d/2))) or A* (BFS + heuristic). For graph traversal, always use a `visited` set to avoid infinite loops on cycles. The mental model: BFS = explore in layers (good for distance); DFS = go deep then backtrack (good for paths and structure). Pick the algorithm based on what the problem asks; the data structure follows.