BFS vs DFS — When to Use Each

// 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;
}

// 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();
}

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;
}