BFS vs DFS — How to Implement Both in Java and When to Use Which

If you’ve ever solved a maze, traversed a file system, or searched for someone in your LinkedIn network, you’ve used an idea that boils down to two fundamental algorithms: BFS and DFS. They’re the simplest graph traversal strategies, yet they underpin everything from web crawlers to AI pathfinding.

What Are BFS and DFS?

Both traverse every reachable node in a graph. The difference is the order in which they visit nodes — and that order changes everything.

         A
       /   \
      B     C
     / \   / \
    D   E F   G

BFS order (level by level): A, B, C, D, E, F, G
DFS order (deep first):     A, B, D, E, C, F, G

BFS explores neighbors first — it fans out level by level. DFS goes as deep as possible down one path before backtracking.

How BFS Works

BFS uses a queue (FIFO). It visits a node, then queues all its unvisited neighbors. The next node to visit is always the one that’s been waiting the longest.

Queue visual:

Step 1: [A]          → visit A, enqueue B, C
Step 2: [B, C]       → visit B, enqueue D, E
Step 3: [C, D, E]    → visit C, enqueue F, G
Step 4: [D, E, F, G] → visit D
Step 5: [E, F, G]    → visit E
Step 6: [F, G]       → visit F
Step 7: [G]          → visit G
Step 8: []           → done

Visit order: A, B, C, D, E, F, G

Key insight: BFS discovers nodes in order of their distance from the start. Everything at distance 1 is visited before anything at distance 2, and so on. This is why BFS finds the shortest path in an unweighted graph.

How DFS Works

DFS uses a stack (LIFO) — either explicitly or via recursion. It plunges down a path until it hits a dead end, then backtracks.

Stack visual (iterative):

Step 1: [A]          → pop A, push C, B
Step 2: [B, C]       → pop B, push E, D
Step 3: [D, E, C]    → pop D
Step 4: [E, C]       → pop E
Step 5: [C]          → pop C, push G, F
Step 6: [F, G]       → pop F
Step 7: [G]          → pop G
Step 8: []           → done

Visit order: A, B, D, E, C, F, G

Key insight: DFS goes deep before wide. It’s memory-efficient for deep graphs and is the natural choice when the solution lies far from the root.

Java Implementation: The Graph

Both algorithms share the same graph representation. An adjacency list is almost always the right choice — it’s memory-efficient and gives O(1) neighbor access.

import java.util.*;

public class Graph {
    private final Map<String, List<String>> adjacencyList = new HashMap<>();

    public void addNode(String node) {
        adjacencyList.putIfAbsent(node, new ArrayList<>());
    }

    public void addEdge(String from, String to) {
        adjacencyList.get(from).add(to);
        adjacencyList.get(to).add(from); // undirected graph
    }

    public List<String> getNeighbors(String node) {
        return adjacencyList.getOrDefault(node, List.of());
    }

    public Set<String> getNodes() {
        return adjacencyList.keySet();
    }
}

BFS — Iterative Implementation

BFS is always iterative. A queue and a visited set are all you need.

import java.util.*;

public class BFS {

    public static List<String> traverse(Graph graph, String start) {
        List<String> visitOrder = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            String current = queue.poll();
            visitOrder.add(current); // process the node

            for (String neighbor : graph.getNeighbors(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        return visitOrder;
    }
}

Critical detail: mark a node as visited when you enqueue it, not when you poll it. Otherwise, the same node can be queued multiple times from different parents, exploding memory on dense graphs.

BFS with Level Tracking

Often you need to know the depth. This variant processes the graph one level at a time:

public static List<List<String>> traverseByLevel(Graph graph, String start) {
    List<List<String>> levels = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    Queue<String> queue = new LinkedList<>();

    queue.add(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<String> currentLevel = new ArrayList<>();

        for (int i = 0; i < levelSize; i++) {
            String current = queue.poll();
            currentLevel.add(current);

            for (String neighbor : graph.getNeighbors(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        levels.add(currentLevel);
    }

    return levels;
}

BFS Shortest Path (Unweighted Graphs)

Since BFS visits nodes in order of distance, adding a parent map gives you the shortest path:

public static List<String> shortestPath(Graph graph, String start, String target) {
    Set<String> visited = new HashSet<>();
    Map<String, String> parent = new HashMap<>();
    Queue<String> queue = new LinkedList<>();

    queue.add(start);
    visited.add(start);
    parent.put(start, null);

    while (!queue.isEmpty()) {
        String current = queue.poll();

        if (current.equals(target)) {
            return reconstructPath(parent, target);
        }

        for (String neighbor : graph.getNeighbors(current)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                parent.put(neighbor, current);
                queue.add(neighbor);
            }
        }
    }

    return List.of(); // no path exists
}

private static List<String> reconstructPath(Map<String, String> parent, String target) {
    List<String> path = new LinkedList<>();
    String current = target;

    while (current != null) {
        path.addFirst(current);
        current = parent.get(current);
    }

    return path;
}

DFS — Recursive Implementation

DFS feels most natural with recursion. The call stack acts as the DFS stack for free.

import java.util.*;

public class DFS {

    public static List<String> traverse(Graph graph, String start) {
        List<String> visitOrder = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        dfsRecursive(graph, start, visited, visitOrder);
        return visitOrder;
    }

    private static void dfsRecursive(
        Graph graph,
        String current,
        Set<String> visited,
        List<String> visitOrder
    ) {
        visited.add(current);
        visitOrder.add(current); // process the node (pre-order)

        for (String neighbor : graph.getNeighbors(current)) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(graph, neighbor, visited, visitOrder);
            }
        }
    }
}

DFS — Iterative Implementation

Sometimes you want DFS without recursion — either to avoid stack overflow on deep graphs or because you prefer explicit control:

public static List<String> traverseIterative(Graph graph, String start) {
    List<String> visitOrder = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    Deque<String> stack = new ArrayDeque<>();

    stack.push(start);

    while (!stack.isEmpty()) {
        String current = stack.pop();

        if (visited.contains(current)) continue;

        visited.add(current);
        visitOrder.add(current);

        // Push neighbors in reverse order to match recursive behavior.
        // Without this, the visit order differs but is still a valid DFS.
        List<String> neighbors = graph.getNeighbors(current);
        for (int i = neighbors.size() - 1; i >= 0; i--) {
            String neighbor = neighbors.get(i);
            if (!visited.contains(neighbor)) {
                stack.push(neighbor);
            }
        }
    }

    return visitOrder;
}

DFS Cycle Detection (Directed Graph)

DFS can detect cycles by tracking nodes currently in the recursion stack:

public static boolean hasCycle(Graph graph) {
    Set<String> visited = new HashSet<>();
    Set<String> inStack = new HashSet<>();

    for (String node : graph.getNodes()) {
        if (!visited.contains(node)) {
            if (hasCycleFrom(graph, node, visited, inStack)) {
                return true;
            }
        }
    }

    return false;
}

private static boolean hasCycleFrom(
    Graph graph,
    String current,
    Set<String> visited,
    Set<String> inStack
) {
    visited.add(current);
    inStack.add(current);

    for (String neighbor : graph.getNeighbors(current)) {
        if (!visited.contains(neighbor)) {
            if (hasCycleFrom(graph, neighbor, visited, inStack)) {
                return true;
            }
        } else if (inStack.contains(neighbor)) {
            // Back edge found — cycle exists
            return true;
        }
    }

    inStack.remove(current); // backtrack
    return false;
}

DFS Topological Sort

For directed acyclic graphs (DAGs), DFS gives you a topological ordering — nodes listed so every edge goes left to right:

public static List<String> topologicalSort(Graph graph) {
    List<String> order = new ArrayList<>();
    Set<String> visited = new HashSet<>();

    for (String node : graph.getNodes()) {
        if (!visited.contains(node)) {
            topologicalDfs(graph, node, visited, order);
        }
    }

    Collections.reverse(order); // post-order reversed = topological order
    return order;
}

private static void topologicalDfs(
    Graph graph,
    String current,
    Set<String> visited,
    List<String> order
) {
    visited.add(current);

    for (String neighbor : graph.getNeighbors(current)) {
        if (!visited.contains(neighbor)) {
            topologicalDfs(graph, neighbor, visited, order);
        }
    }

    order.add(current); // post-order: add after children
}

BFS vs DFS: Side-by-Side Comparison

When to Use BFS

Use BFS when any of these apply:

• Shortest path in an unweighted graph — BFS visits nodes in order of distance, guaranteeing the first time you reach a target is via the shortest path. Word ladder, minimum moves in a grid, degrees of separation.
• Level-order traversal — You need nodes grouped by depth. Printing a binary tree level by level, finding all nodes at distance K.
• The solution is near the start — BFS searches locally first. If the answer is close, BFS finds it fast without wandering deep.
• You’re searching a web of relationships — Friend recommendations, “people you may know,” finding the closest connection.

Concrete problems where BFS shines:

// Find the minimum number of moves in a grid maze
// Shortest transformation sequence (word ladder)
// Rotting oranges — spread level by level
// Find all nodes K distance away in a tree
// Check if a binary tree is complete

When to Use DFS

Use DFS when any of these apply:

• You need to explore entire search space — DFS exhaustively visits every branch. Puzzle solving, constraint satisfaction, generating all subsets or permutations.
• The solution is deep — If you suspect the answer lies far from the root, DFS gets there without the memory overhead of BFS.
• Backtracking problems — N-Queens, Sudoku, maze generation. DFS naturally unwinds the call stack when a path fails, returning you to the last decision point.
• Cycle detection — DFS with a recursion stack detects cycles in directed graphs cleanly.
• Topological ordering — Build systems, dependency resolution, course prerequisite chains. DFS post-order reversed gives you a valid topological sort.
• You need to discover structure — Connected components, bridges in a graph, articulation points, strongly connected components (Kosaraju’s or Tarjan’s algorithm).

Concrete problems where DFS shines:

// Generate all valid parentheses combinations
// N-Queens placement
// Find all paths from source to target
// Check if a binary tree is balanced
// Serialize / deserialize a binary tree
// Detect cycle in a directed graph
// Count connected components
// Solve a Sudoku puzzle

Real-World Decision Framework

Ask yourself these three questions:

1. Do I need the shortest path in an unweighted graph?
   Yes → Use BFS.
   No  → Continue.

2. Am I searching a very wide graph where memory matters?
   Yes → Use DFS (or iterative deepening DFS).
   No  → Continue.

3. Is the solution likely deep, or am I doing exhaustive search?
   Yes → Use DFS.
   No  → Use BFS (it's usually more intuitive and safer).

Common Pitfalls

BFS Pitfall: Forgetting to Mark Visited on Enqueue

// ❌ Wrong: mark on poll — leads to duplicates
queue.add(start);
while (!queue.isEmpty()) {
    String node = queue.poll();
    visited.add(node);          // too late
    for (String neighbor : graph.getNeighbors(node)) {
        if (!visited.contains(neighbor)) {
            queue.add(neighbor); // neighbor might already be in queue
        }
    }
}

// ✅ Correct: mark on enqueue
queue.add(start);
visited.add(start);             // immediately
while (!queue.isEmpty()) {
    String node = queue.poll();
    for (String neighbor : graph.getNeighbors(node)) {
        if (!visited.contains(neighbor)) {
            visited.add(neighbor); // before it enters the queue
            queue.add(neighbor);
        }
    }
}

DFS Pitfall: Stack Overflow on Deep Graphs

Recursive DFS crashes when the graph is deeper than the call stack limit (typically ~10,000 frames in Java). Switch to the iterative version or increase the stack size:

java -Xss4m Main    # 4 MB stack size instead of default 1 MB

DFS Pitfall: Not Handling Disconnected Graphs

Both BFS and DFS only visit nodes reachable from the start. If your graph has disconnected components, wrap the call in a loop:

for (String node : graph.getNodes()) {
    if (!visited.contains(node)) {
        traverse(graph, node); // starts fresh from each unvisited component
    }
}

The Bottom Line

BFS and DFS are the same idea with a different data structure — queue vs stack. That one difference changes everything about what they’re good for.

• BFS = shortest path, level order, close targets. Use a queue.
• DFS = exhaustive search, backtracking, deep targets. Use recursion or a stack.

Both run in O(V + E) time with an adjacency list. Both are dead simple to implement. The skill is knowing which one fits your problem.

If you remember only one thing: BFS finds the shortest path; DFS explores everything. Match that to your goal.

Pro Tip: If you need the shortest path but the graph is too wide for BFS’s memory, use Iterative Deepening DFS (IDDFS). It runs DFS with a depth limit, increases the limit each iteration, and combines DFS’s O(depth) memory with BFS’s shortest-path guarantee. It does repeat work, but the overhead is surprisingly small — the final level dominates the total node count in most graphs.