BFS & DFS

The visited set: rule zero

Before either algorithm, one non-negotiable rule. Trees have no cycles, so walking downward can never revisit a node. Graphs make no such promise. Follow edges naively around a cycle like A to B to C to A and your code loops forever.

The fix is a visited set: the moment you decide a node will be processed, record it, and never process a recorded node again. In Java that is a boolean[] visited when nodes are numbered 0 to n - 1, or a HashSet for anything else. Every node is processed once and every edge examined a constant number of times, so both BFS and DFS run in O(n + e) time for n nodes and e edges. Forgetting the visited set is the classic graph bug: infinite loops on cyclic graphs, or exponential blowup from re-exploring shared paths.

BFS: explore in rings with a queue

BFS uses a queue. First in, first out. Start by marking and enqueueing the source node. Then loop: dequeue a node, process it, and enqueue each unvisited neighbor, marking them visited as they go in. Because the queue serves nodes in arrival order, every node one edge away from the source is handled before any node two edges away, and so on outward in rings.

That ring-by-ring order is BFS's superpower: the first time BFS reaches any node, it has arrived by a path with the fewest possible edges. So in an unweighted graph, BFS from the source computes shortest paths for free, just count the rings. This is the same level-order traversal you saw on trees, generalized with a visited set.

One habit worth building: mark nodes visited when you enqueue them, not when you dequeue them. Otherwise the same node can be added to the queue several times through different neighbors before it is ever processed.

void bfs(List<List<Integer>> adj, int start) {
    boolean[] visited = new boolean[adj.size()];
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.add(start);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println(node);
        for (int next : adj.get(node)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.add(next);
            }
        }
    }
}

DFS: dive deep, then backtrack

DFS explores like a maze-runner with a ball of string: pick a neighbor, go there, pick one of its neighbors, keep going until you hit a dead end (a node with no unvisited neighbors) then backtrack to the most recent junction and try a different branch.

The cleanest implementation is recursion: mark the node visited, then recursively visit each unvisited neighbor. The call stack silently plays the role of the ball of string, remembering the way back. An equivalent iterative version replaces recursion with an explicit stack (last in, first out) and looks almost identical to BFS with the queue swapped for a stack. Worth knowing because very deep graphs can overflow Java's call stack.

DFS does not find shortest paths. It may wander a long way around before stumbling onto a nearby node. Its strengths are different: it naturally explores entire connected regions, detects cycles, and underpins backtracking and topological sorting.

void dfs(List<List<Integer>> adj, int node, boolean[] visited) {
    visited[node] = true;
    System.out.println(node);
    for (int next : adj.get(node)) {
        if (!visited[next]) {
            dfs(adj, next, visited);
        }
    }
}

Which one, when?

Both visit the same nodes in O(n + e); the difference is order, and problems usually tell you which order matters. Reach for BFS when the problem says shortest, fewest, minimum steps, or nearest in an unweighted graph, that ring-by-ring guarantee is exactly what those questions need. Reach for DFS when you must explore or count whole regions (connected components, island counting), detect cycles, enumerate paths, or when you simply need any traversal and want the shortest code.

Memory profiles differ too: BFS's queue can hold an entire ring, which is wide in bushy graphs, while DFS's stack holds one path, which is deep in stringy graphs. Most interview instincts, though, come down to: shortest anything means BFS; everything-in-a-region means DFS.

Grids are graphs in disguise

A huge family of interview problems (number of islands, rotting oranges, flood fill, shortest path in a maze) takes place on a 2D grid. No one hands you an adjacency list, because you do not need one: each cell (r, c) is a node, and its edges go to the four cells up, down, left, and right. Generate neighbors on the fly with a direction array like {{1,0},{-1,0},{0,1},{0,-1}}, skipping coordinates that fall off the board.

Everything else transfers unchanged: a boolean[rows][cols] visited grid, a queue of coordinate pairs for BFS, recursion on cells for DFS. Count islands by scanning every cell and launching a DFS from each unvisited land cell, each launch consumes exactly one island. Find the fastest way through a maze with BFS, counting rings.

BFS and DFS answer is there a path and how short is it. But some problems ask thousands of connectivity questions while edges keep being added. Are these two nodes in the same group yet? Re-running a traversal per query is wasteful, and the next structure, Union-Find, answers each one in practically constant time.

Frequently asked