Choosing Between Breadth-First and Depth-First Search

Welcome back. In the last lesson, you used heaps when a problem repeatedly needed the most important boundary item: the weakest retained top-$k$ candidate, the earliest meeting end time, or the highest-priority job. Graph traversal poses a different question: given a network of possible moves or relationships, which vertices should we explore next?

This lesson develops the interview skill of selecting the traversal from the requirement rather than from habit:

• use breadth-first search (BFS) when the prompt needs the fewest moves or edges in an unweighted graph, distances by layer, or the nearest reachable target;
• use depth-first search (DFS) when the prompt needs systematic exploration, reachability, connected components, or a deep branch-oriented search.

You will implement both in Java, state their invariants, and recognize cases where neither is the correct shortest-path algorithm. Study time: about 40 minutes.

---

1. Turn the prompt into a graph before choosing an algorithm

A graph consists of:

• vertices, representing states, objects, users, services, locations, courses, or grid cells;
• edges, representing valid transitions or relationships between those vertices.

Interview prompts may not use graph terminology. These are all graph problems:

Prompt language	Vertex	Edge
“Can user A reach user B through follows?”	User	Follow relationship
“Minimum moves through a maze”	Open grid cell	Legal move to an adjacent cell
“How many isolated server clusters exist?”	Server	Network connection
“Can these prerequisites all be completed?”	Course or task	Dependency
“Is there a transformation from one word to another?”	Valid word	One allowed transformation

The graph may be:

• Undirected: a connection works in both directions, such as a friendship or a physical cable.
• Directed: a transition has one allowed direction, such as a service dependency, hyperlink, or course prerequisite.
• Explicit: supplied as an adjacency list.
• Implicit: generated as you explore, as in a grid or state-space problem.

For a graph stored as an adjacency list, Java commonly represents it as:

List<List<Integer>> graph;

Here, graph.get(v) contains the neighbors that can be visited directly from vertex v.

A traversal must track which vertices have already been discovered. Without that protection, a cycle can cause repeated work or an infinite loop:

0 connected to 1
1 connected to 2
2 connected to 0

The key choice is the structure holding the frontier: discovered vertices whose neighbors have not yet been fully explored.

• BFS keeps the frontier in a FIFO queue.
• DFS keeps the frontier in a LIFO stack, either explicitly or through recursive calls.

The queue is the same FIFO concept that appeared in the previous lesson’s scheduling discussion, but it now determines the correctness of shortest paths.

---

2. The traversal shape: layers versus deep branches

BFS expands outward in layers. Starting from a source, it examines every vertex one edge away before vertices two edges away, then vertices three edges away, and so on.

DFS instead follows one available branch as far as it can before returning to explore alternatives.

Do not treat a displayed traversal order as universal. If a vertex has several neighbors, the order of its adjacency list affects the exact order printed by either algorithm. What matters is the structural guarantee:

Traversal	Frontier structure	Structural guarantee
BFS	FIFO queue	Vertices are processed in nondecreasing number of edges from the source
DFS	LIFO stack or recursion	A branch is explored deeply before sibling branches

The following Java-focused video gives a useful visual trace of BFS and its queue invariant.

A concise way to say this in an interview is:

“BFS uses a FIFO queue, so it exhausts all vertices at distance $d$ before processing any vertex at distance $d+1$. DFS uses a stack, so it commits to one branch before returning to deferred alternatives.”

---

3. BFS: shortest path means fewest edges

BFS is the correct default when the question asks for:

• the fewest moves;
• the shortest path in an unweighted graph;
• the minimum number of transformations;
• the nearest matching state;
• the distance from a source to every reachable vertex;
• the nearest source when several sources are possible.

“Unweighted” means each edge has identical cost. BFS minimizes the number of edges. If every move costs one unit, that also minimizes total cost.

Consider this directed graph, where the adjacency order of vertex 0 is [1, 2]:

0 connects to 1 and 2
1 connects to 3
3 connects to 4
4 connects to 5
2 connects to 5

A DFS that follows the first available neighbor can reach 5 through the long route containing five vertices. BFS discovers 2 at distance $1$, then discovers 5 from 2 at distance $2$. The BFS route is therefore shorter.

The BFS invariant

For a source vertex $s$:

When a vertex is first marked and placed into the queue, the stored distance is the minimum number of edges from $s$ to that vertex.

Why does this hold? Initially, the queue contains only $s$, whose distance is $0$. When BFS removes a vertex at distance $d$, every newly discovered neighbor is exactly $d+1$ edges away. Because the queue already contains all previously discovered vertices at distance $d$, no undiscovered route with fewer than $d+1$ edges can appear later.

A reusable Java shortest-path template

This implementation returns one shortest path from source to target. The parent array plays two roles:

1. parent[v] == -1 means vertex v has not been discovered.
2. Otherwise, parent[v] records the vertex from which v was first reached.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.List;

public class GraphSearch {

    static List<Integer> shortestPath(
            List<List<Integer>> graph,
            int source,
            int target
    ) {
        int n = graph.size();

        int[] parent = new int[n];
        Arrays.fill(parent, -1);

        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(source);
        parent[source] = source;

        while (!queue.isEmpty()) {
            int current = queue.removeFirst();

            if (current == target) {
                break;
            }

            for (int next : graph.get(current)) {
                if (parent[next] == -1) {
                    parent[next] = current;
                    queue.addLast(next);
                }
            }
        }

        if (parent[target] == -1) {
            return List.of();
        }

        List<Integer> path = new ArrayList<>();

        for (int vertex = target;
                vertex != source;
                vertex = parent[vertex]) {
            path.add(vertex);
        }

        path.add(source);
        Collections.reverse(path);

        return path;
    }
}

Two details are especially important.

Mark when discovered, not when removed. Setting parent[next] before adding next to the queue prevents the same vertex from being inserted many times through different incoming edges.

Use ArrayDeque. It supports queue behavior cleanly:

• addLast() adds a newly discovered vertex to the back;
• removeFirst() removes the oldest pending vertex from the front.

Avoid Stack; it is a legacy class. ArrayDeque works well for both BFS queues and iterative DFS stacks.

Distances without reconstructing paths

If the prompt asks only for shortest distance, store a distance array instead of, or alongside, parent.

static int[] shortestDistances(
        List<List<Integer>> graph,
        int source
) {
    int n = graph.size();
    int[] distance = new int[n];
    Arrays.fill(distance, -1);

    Deque<Integer> queue = new ArrayDeque<>();
    queue.addLast(source);
    distance[source] = 0;

    while (!queue.isEmpty()) {
        int current = queue.removeFirst();

        for (int next : graph.get(current)) {
            if (distance[next] == -1) {
                distance[next] = distance[current] + 1;
                queue.addLast(next);
            }
        }
    }

    return distance;
}

An unreachable vertex remains -1. This is a common pattern in maze, grid, and “shortest reach” questions.

Multi-source BFS

If the prompt asks for the nearest hospital, charging station, exit, or initial infected machine, initialize BFS with all sources:

1. Mark every source at distance $0$.
2. Put every source into the queue.
3. Run the usual BFS loop.

The resulting distance for each reachable vertex is its minimum distance to any source. The first source to discover it is necessarily one of its nearest sources.

---

4. DFS: systematic exploration without a shortest-path guarantee

DFS is excellent when the problem does not require a minimum-edge answer and you want to explore a connected region or a full branch of possibilities.

Typical DFS-friendly requirements include:

• “Can the target be reached at all?”
• “How many connected components are there?”
• “Mark every cell in this island.”
• “Does a graph contain a cycle?”
• “Explore a nested structure.”
• “Try one choice, continue deeply, then backtrack.”

Both BFS and DFS can answer a simple reachability question. DFS is often chosen because it is concise and natural for region exploration. But if the requirement says shortest, minimum moves, closest, or fewest transformations, choose BFS instead.

Iterative DFS in Java

This method answers whether target is reachable from source:

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

public class DepthFirstSearch {

    static boolean reachable(
            List<List<Integer>> graph,
            int source,
            int target
    ) {
        boolean[] visited = new boolean[graph.size()];

        Deque<Integer> stack = new ArrayDeque<>();
        stack.addLast(source);
        visited[source] = true;

        while (!stack.isEmpty()) {
            int current = stack.removeLast();

            if (current == target) {
                return true;
            }

            for (int next : graph.get(current)) {
                if (!visited[next]) {
                    visited[next] = true;
                    stack.addLast(next);
                }
            }
        }

        return false;
    }
}

The DFS invariant is:

Every vertex in the stack has been discovered but not yet processed, and every marked vertex has already been discovered from the source.

The only operational difference from BFS is decisive:

• BFS removes with removeFirst().
• DFS removes with removeLast().

That one choice changes the exploration order from layers to depth.

Connected components: DFS from every unvisited vertex

A graph may be disconnected. Starting DFS from a single source explores only that source’s component.

To count all components in an undirected graph:

1. Create one global visited array.
2. Scan every vertex.
3. When an unvisited vertex is found, begin a DFS from it.
4. Increment the component count once for that DFS.

Every DFS started by the outer loop marks exactly one previously unseen connected component.

This is the pattern behind problems such as “Number of Islands,” “count provinces,” and “count disconnected server networks.” BFS would also work, but DFS is commonly used because a component can be fully explored before moving to the next unvisited starting point.

Recursive DFS and its limitation

Recursive DFS is compact:

static void dfs(
        List<List<Integer>> graph,
        int current,
        boolean[] visited
) {
    visited[current] = true;

    for (int next : graph.get(current)) {
        if (!visited[next]) {
            dfs(graph, next, visited);
        }
    }
}

However, a very deep graph can exceed the Java call stack and throw StackOverflowError. For production-scale or adversarial input, prefer the iterative ArrayDeque implementation.

---

5. Use the requirement, not the algorithm name, to decide

The following guide is more useful than memorizing isolated definitions.

Requirement in the prompt	Best initial choice	Why
Fewest edges, minimum moves, shortest transformation	BFS	FIFO processing explores by distance layer
Nearest target or nearest source	BFS	The first discovered target is at minimum edge distance
Distance to all vertices in an unweighted graph	BFS	Distances are assigned in layer order
Reachability only	DFS or BFS	Both visit all reachable vertices; DFS is often simpler
Count connected regions or islands	DFS or BFS	Traverse one component at a time; DFS is conventional
Explore one branch deeply, with possible backtracking	DFS	LIFO behavior preserves branch-oriented exploration
Detect directed dependency cycles or derive dependency ordering	DFS	Entry and return structure is useful for these tasks
Different nonnegative edge costs	Neither plain BFS nor plain DFS	Use a weighted shortest-path algorithm such as Dijkstra’s algorithm

The last row is a frequent interview trap. BFS does not solve a general weighted shortest-path problem merely because it uses a queue.

For example, if one edge costs $100$ and another route uses three edges costing $1$ each, BFS would prefer the one-edge route even though its total cost is higher. BFS is correct only when every edge has equal cost, or when minimizing edge count is exactly the stated objective.

The Princeton Algorithms reference gives a concise formal account of the distinction.

---

6. Complexity and interview explanation

With an adjacency-list representation, both BFS and DFS have time complexity:

$$O(V+E)$$

where:

• $V$ is the number of vertices;
• $E$ is the number of edges.

Each reachable vertex is marked once. Each adjacency list is scanned once, so every edge is considered a constant number of times.

Their auxiliary space complexity is:

$$O(V)$$

This includes the visited, parent, or distance arrays, plus the queue or stack.

The shape of memory use differs:

• BFS may hold a wide frontier containing many vertices from the same layer.
• DFS may build a deep stack when the graph has a long chain.

This distinction can matter for very large graphs, but correctness comes first. Do not choose DFS for a shortest-path prompt simply because its frontier might sometimes be smaller.

A strong interview response template

For an unweighted shortest-path question:

“I model each state as a vertex and each legal move as an edge. Because the prompt asks for the minimum number of moves and every move has equal cost, I use BFS. The FIFO queue processes states by increasing distance from the source. I mark a vertex when I enqueue it so it enters the queue once, record its parent if I need the path, and return the first path discovered to the target. The time complexity is $O(V+E)$, with $O(V)$ extra space.”

For a component or reachability question:

“The task only requires exhaustive exploration, not a shortest path, so I use DFS. I maintain a visited array to avoid revisiting cycles. For components, I run DFS from each unvisited vertex; each new traversal identifies one component. The overall complexity is $O(V+E)$.”

---

Key takeaways

• BFS and DFS both prevent repeated exploration with a visited structure, and both run in:

$$O(V+E)$$

for adjacency-list graphs.

• BFS uses a FIFO queue and explores vertices by distance layers. It is the right choice for shortest paths measured in number of edges, minimum moves, nearest targets, and unweighted distances.
• DFS uses a LIFO stack or recursion and explores a branch deeply before returning. It is well suited to reachability, connected components, flood fill, cycle-oriented exploration, and backtracking-style search.
• The phrase “shortest path” is incomplete without edge-cost information. Plain BFS is correct when all edges have equal cost; it is not a general weighted shortest-path algorithm.
• Mark a vertex when it is discovered and added to the frontier, not after duplicates have already accumulated.
• In Java, use ArrayDeque for both queues and stacks.

Next, you will move from traversal to optimization over overlapping subproblems: dynamic programming. You will learn to formulate a state, recurrence, and base cases for a sequence problem.