BFS and DFS — The Two Traversals That Power Everything

Every graph algorithm you will learn in this phase is BFS or DFS with one additional idea layered on top. Dijkstra is BFS on a priority queue. Topological sort is DFS with a finish-time stack. Cycle detection is DFS with a color scheme. If you own BFS and DFS deeply — their mechanics, their invariants, their failure modes — every other algorithm becomes a variation rather than something new to memorize.

This file is the longest in Phase 3. That reflects the importance. Spend proportional time here.

---

BFS — Breadth-First Search

BFS explores a graph layer by layer. From a starting node, it visits all nodes at distance 1, then all nodes at distance 2, and so on. This layer property is the source of its key capability: BFS finds shortest paths in unweighted graphs.

Core Implementation

void bfs(int start, List<List<Integer>> adj, int V) {
    boolean[] visited = new boolean[V];
    Queue<Integer> queue = new LinkedList<>();

    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println("Visiting: " + node);

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

Time: O(V + E). Every vertex is enqueued and dequeued once. Every edge is examined at most twice (for undirected graphs). Space: O(V) for the queue and visited array.

---

Why BFS Finds Shortest Paths (Proof by Level Invariant)

The claim: BFS discovers each node at the minimum number of hops from the source.

Proof sketch: BFS processes nodes in non-decreasing order of distance from the source. This is the level invariant: all nodes at distance d are enqueued before any node at distance d+1, because nodes at distance d+1 are neighbors of nodes at distance d, and neighbors are enqueued only when their parent is dequeued. Since we mark visited on enqueue (not dequeue), a node is only enqueued once — on its first discovery, which is necessarily via the shortest path.

This only works for unweighted graphs. If edges have different weights, BFS may process a node via a longer path first if that path has fewer hops. Dijkstra fixes this by processing nodes in order of total accumulated weight, not number of hops.

// BFS for shortest path distance from source
int[] shortestPath(int source, List<List<Integer>> adj, int V) {
    int[] dist = new int[V];
    Arrays.fill(dist, -1);

    Queue<Integer> queue = new LinkedList<>();
    dist[source] = 0;
    queue.offer(source);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbor : adj.get(node)) {
            if (dist[neighbor] == -1) {          // unvisited
                dist[neighbor] = dist[node] + 1;
                queue.offer(neighbor);
            }
        }
    }
    return dist;  // dist[i] = shortest hop-count from source to i; -1 if unreachable
}

---

BFS Application: Multi-Source BFS

Sometimes you need shortest distance from any of several sources, not just one. Instead of running BFS from each source and taking the minimum (O(V × (V+E))), run a single BFS initialized with all sources simultaneously. This is O(V+E).

// Example: Walls and Gates (LC 286)
// Grid cells: -1 (wall), 0 (gate), INF (empty room)
// Fill each empty room with its distance to the nearest gate

void wallsAndGates(int[][] rooms) {
    int rows = rooms.length, cols = rooms[0].length;
    Queue<int[]> queue = new LinkedList<>();

    // Initialize queue with ALL gate positions
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (rooms[r][c] == 0)
                queue.offer(new int[]{r, c});

    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        int r = cell[0], c = cell[1];
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && rooms[nr][nc] == Integer.MAX_VALUE) {
                rooms[nr][nc] = rooms[r][c] + 1;
                queue.offer(new int[]{nr, nc});
            }
        }
    }
}

Multi-source BFS is the right approach for: “nearest X to every Y,” “minimum distance to any boundary,” “01 matrix” (LC 542).

---

0-1 BFS (Deque Trick)

When edge weights are either 0 or 1, you can get Dijkstra-like shortest paths in O(V+E) instead of O((V+E) log V) by using a deque instead of a priority queue:

• Weight 0 edge to neighbor: push to front of deque (same cost level)

• Weight 1 edge to neighbor: push to back of deque (next cost level)

int[] zeroOneBFS(int source, int V, List<int[]>[] adj) {
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    Deque<Integer> deque = new ArrayDeque<>();
    deque.offerFirst(source);

    while (!deque.isEmpty()) {
        int node = deque.pollFirst();
        for (int[] edge : adj[node]) {          // edge = {neighbor, weight (0 or 1)}
            int neighbor = edge[0], w = edge[1];
            if (dist[node] + w < dist[neighbor]) {
                dist[neighbor] = dist[node] + w;
                if (w == 0) deque.offerFirst(neighbor);
                else        deque.offerLast(neighbor);
            }
        }
    }
    return dist;
}

Use case: minimum number of flips, minimum cost path where some moves are free.

---

The Bidirectional BFS Trick

Standard BFS from source to target: search space grows as O(b^d) where b is branching factor and d is distance.

Bidirectional BFS: simultaneously BFS from source forward and from target backward. The two frontiers meet in the middle. Search space: O(b^(d/2)) + O(b^(d/2)) = O(b^(d/2)). For b=10 and d=10, this is 10^5 vs 10^10 — several orders of magnitude.

Use case: word ladder (LC 127). The speedup is real and measurable for problems with large search spaces.

---

DFS — Depth-First Search

DFS plunges as deep as possible along one path before backtracking. Unlike BFS, it doesn’t give shortest paths, but it provides access to structural information BFS cannot: topological ordering, cycle detection, strongly connected components, and tree structure.

Core Implementation (Recursive)

void dfs(int node, boolean[] visited, List<List<Integer>> adj) {
    visited[node] = true;
    System.out.println("Entering: " + node);    // preorder (discover time)

    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, adj);
        }
    }

    System.out.println("Finishing: " + node);   // postorder (finish time)
}

Core Implementation (Iterative, using explicit stack)

void dfsIterative(int start, List<List<Integer>> adj, int V) {
    boolean[] visited = new boolean[V];
    Deque<Integer> stack = new ArrayDeque<>();

    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited[node]) continue;    // may be pushed multiple times
        visited[node] = true;

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                stack.push(neighbor);
            }
        }
    }
}

Note: the iterative version marks visited on pop, not push, because the same node can be pushed multiple times by different neighbors before it’s processed. This differs from BFS where marking on enqueue prevents duplicate enqueues.

---

DFS Timing: Discover and Finish Times

The recursive DFS naturally produces two timestamps per node:

• Discover time: when DFS enters the node

• Finish time: when DFS exits (all subtrees explored)

These times encode the entire tree structure. Specifically:

• If u’s interval [d_u, f_u] contains v’s interval [d_v, f_v], then u is an ancestor of v in the DFS tree.

• Topological order = reverse order of finish times (in a DAG).

---

DFS Applications

1. Cycle Detection in Undirected Graphs

A cycle exists if DFS visits a node that is already visited AND is not the direct parent of the current node.

boolean hasCycleUndirected(int node, int parent, boolean[] visited, List<List<Integer>> adj) {
    visited[node] = true;

    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            if (hasCycleUndirected(neighbor, node, visited, adj)) return true;
        } else if (neighbor != parent) {
            return true;    // visited neighbor that isn't our parent = back edge = cycle
        }
    }
    return false;
}

What most people get wrong: using this undirected technique for directed graphs. In a directed graph, reaching a visited node does NOT mean a cycle exists — it may just be a cross edge from one branch to another. Directed graph cycle detection requires three-color DFS (see below).

---

2. Cycle Detection in Directed Graphs (Three-Color DFS)

Three states per node:

• White (0): unvisited

• Gray (1): currently on the DFS path (in the call stack)

• Black (2): fully processed (all descendants explored)

A cycle exists if DFS reaches a gray node. Reaching a black node is fine — it’s just a cross edge.

int[] color;   // 0=white, 1=gray, 2=black

boolean hasCycleDirected(int node) {
    color[node] = 1;    // mark gray (in progress)

    for (int neighbor : adj.get(node)) {
        if (color[neighbor] == 1) return true;    // back edge to gray = cycle
        if (color[neighbor] == 0) {               // white = unvisited
            if (hasCycleDirected(neighbor)) return true;
        }
        // black: already done, skip
    }

    color[node] = 2;    // mark black (done)
    return false;
}

// Call from main:
color = new int[V];  // all white initially
for (int i = 0; i < V; i++)
    if (color[i] == 0)
        if (hasCycleDirected(i)) return true;

---

3. Connected Components (Undirected)

Already established in fundamentals: loop over all vertices, trigger DFS/BFS for each unvisited one.

int countComponents(int V, int[][] edges) {
    List<List<Integer>> adj = buildAdj(V, edges);
    boolean[] visited = new boolean[V];
    int count = 0;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            count++;
            dfs(i, visited, adj);
        }
    }
    return count;
}

4. Flood Fill (LC 733)

Grid BFS/DFS from a starting cell, changing the color of all connected cells with the same original color. This is just connected component detection on a grid.

void floodFill(int[][] image, int sr, int sc, int newColor) {
    int originalColor = image[sr][sc];
    if (originalColor == newColor) return;   // avoid infinite loop
    dfs(image, sr, sc, originalColor, newColor);
}

void dfs(int[][] image, int r, int c, int orig, int newColor) {
    if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
    if (image[r][c] != orig) return;

    image[r][c] = newColor;    // mark visited by changing color
    dfs(image, r+1, c, orig, newColor);
    dfs(image, r-1, c, orig, newColor);
    dfs(image, r, c+1, orig, newColor);
    dfs(image, r, c-1, orig, newColor);
}

Using the grid value itself as the visited marker (changing to newColor) avoids a separate visited array. Only valid when the new value is distinguishable from the old.

---

BFS vs DFS: When to Use Which

Need	Use	Why
Shortest path (unweighted)	BFS	Level invariant guarantees minimum hops
Cycle detection (undirected)	Either	Both work
Cycle detection (directed)	DFS (3-color)	BFS doesn’t naturally produce back-edge detection
Topological sort	DFS or BFS (Kahn’s)	DFS gives finish-time order; Kahn’s is BFS on in-degree
Connected components	Either	Both work equally well
Path existence	Either	DFS is simpler; BFS finds shortest
Level/layer information	BFS	Level structure is natural in BFS
Maze / flood fill	Either	DFS is simpler; BFS gives minimum path

---

Practice Problems

#	Problem	Difficulty	Focus
1	LC 200 — Number of Islands	Medium	BFS/DFS on grid, connected components
2	LC 994 — Rotting Oranges	Medium	Multi-source BFS, level timing
3	LC 542 — 01 Matrix	Medium	Multi-source BFS from all 0s simultaneously
4	LC 695 — Max Area of Island	Medium	DFS with area accumulation
5	LC 127 — Word Ladder	Hard	BFS shortest path in implicit graph
6	LC 207 — Course Schedule	Medium	DFS cycle detection in directed graph
7	LC 417 — Pacific Atlantic Water Flow	Medium	Multi-source BFS from two borders
8	LC 130 — Surrounded Regions	Medium	BFS from border, mark safe cells

Do problems 1, 2, 3 first — they establish BFS fluency. Then 4 and 6 for DFS. Problem 5 (Word Ladder) is the payoff problem: each word is a node, edges connect words differing by one character. The graph is never explicitly built — you construct neighbors on the fly during BFS.

---

Navigation

← Previous	01 — Graph Fundamentals
→ Next	03 — Topological Sort
↑ Phase Home	Phase 3 README
⌂ Root	Master README