BFS vs DFS

"When BFS beats DFS and vice versa. Shortest path, topological, bipartite, connected components, backtracking."

Deep Dive Tutorial

BFS and DFS both visit every node in a graph/tree, but they answer different questions. BFS finds the shortest path in unweighted graphs. DFS finds connected components, detects cycles, computes topological order, and enables backtracking. Choosing the wrong one either gives a wrong answer or TLEs.

Question	Use	Why
Shortest path (unweighted)	BFS	Explores level-by-level — first time you reach a node is the shortest
Connected components	DFS	Flood-fill: mark all reachable nodes from a starting point
Cycle detection	DFS	Track state: unvisited → visiting → visited (3-color)
Topological sort	DFS (Kahn's BFS)	DFS finish time ordering; or BFS on indegree-0 nodes
Level-order output	BFS	Each queue flush = one level
Backtracking / all paths	DFS	Recursion with undo naturally models path exploration
Grid: min steps to reach target	BFS	Each step costs 1 — BFS gives shortest automatically
Grid: flood fill / connected region size	DFS	Simpler recursive mark-and-expand
SCC (strongly connected)	DFS × 2	Kosaraju: DFS finish order + DFS on reverse graph

BFS Template (Level-Aware)

BFS — shortest path, level-order, multi-source

// Single-source BFS
function bfs(graph, start) {
    const visited = new Set([start]);
    let queue = [start];
    let level = 0;
    while (queue.length) {
        const nextQueue = [];
        for (const node of queue) {
            // process node at distance 'level'
            for (const neighbor of graph[node]) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    nextQueue.push(neighbor);
                }
            }
        }
        queue = nextQueue;
        level++;
    }
}

// Multi-source BFS (start from multiple nodes simultaneously)
// Used for: 01 Matrix, Rotting Oranges, walls-and-gates
function multiSourceBFS(grid, sources) {
    const dist = Array.from(grid, r => new Array(r.length).fill(Infinity));
    let queue = [];
    for (const [r, c] of sources) { dist[r][c] = 0; queue.push([r, c]); }
    const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
    while (queue.length) {
        const [r, c] = queue.shift();
        for (const [dr, dc] of dirs) {
            const nr = r+dr, nc = c+dc;
            if (nr>=0 && nr<grid.length && nc>=0 && nc<grid[0].length
                && dist[nr][nc]===Infinity) {
                dist[nr][nc] = dist[r][c] + 1;
                queue.push([nr, nc]);
            }
        }
    }
    return dist;
}

DFS Template (With State)

DFS — cycle detection, components, topo sort

// Iterative DFS (avoids stack overflow on large graphs)
function dfsIterative(graph, start) {
    const visited = new Set();
    const stack = [start];
    while (stack.length) {
        const node = stack.pop();
        if (visited.has(node)) continue;
        visited.add(node);
        for (const neighbor of graph[node])
            if (!visited.has(neighbor)) stack.push(neighbor);
    }
}

// Recursive DFS with 3-color cycle detection
// WHITE=0 (unvisited), GRAY=1 (in current path), BLACK=2 (done)
function hasCycle(graph, n) {
    const color = new Array(n).fill(0);
    const dfs = (node) => {
        color[node] = 1; // GRAY — currently visiting
        for (const neighbor of graph[node]) {
            if (color[neighbor] === 1) return true;  // back edge = cycle
            if (color[neighbor] === 0 && dfs(neighbor)) return true;
        }
        color[node] = 2; // BLACK — fully processed
        return false;
    };
    for (let i = 0; i < n; i++)
        if (color[i] === 0 && dfs(i)) return true;
    return false;
}

// DFS postorder = reverse topological sort
function topoSort(graph, n) {
    const visited = new Set(), order = [];
    const dfs = (node) => {
        visited.add(node);
        for (const nb of graph[node]) if (!visited.has(nb)) dfs(nb);
        order.push(node); // push AFTER all descendants
    };
    for (let i = 0; i < n; i++) if (!visited.has(i)) dfs(i);
    return order.reverse();
}

Key Pattern: 0-1 BFS (Two-Queue / Deque)

lightbulb

0-1 BFS: Edge weights are only 0 or 1. Use a deque: push weight-0 edges to the front, weight-1 edges to the back. Gives O(V+E) shortest path — faster than Dijkstra's O((V+E) log V) for this case.

Used when: moving in a direction costs 0 (free move, teleport) or 1 (step), and you want minimum cost.

0-1 BFS with deque

function zerOneBFS(graph, start, n) {
    const dist = new Array(n).fill(Infinity);
    dist[start] = 0;
    const deque = [start]; // front = cost 0, back = cost 1
    while (deque.length) {
        const u = deque.shift();
        for (const [v, w] of graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w === 0) deque.unshift(v); // free edge → front
                else deque.push(v);             // cost-1 edge → back
            }
        }
    }
    return dist;
}