🔍 JavaScript Graph Traversal

BFS — Breadth-First Search

function bfs(graph, start) {
    const visited = new Set([start]);
    const queue   = [start];
    const result  = [];
    while (queue.length) {
        const node = queue.shift();
        result.push(node);
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return result;
}

Time: O(V + E) | Space: O(V)

---

BFS — Shortest Path (Unweighted)

function shortestPath(graph, src, dst) {
    const visited = new Set([src]);
    const queue   = [[src, 0]];
    while (queue.length) {
        const [node, dist] = queue.shift();
        if (node === dst) return dist;
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([neighbor, dist + 1]);
            }
        }
    }
    return -1;
}

---

DFS — Recursive

function dfs(graph, node, visited = new Set()) {
    visited.add(node);
    console.log(node);
    for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) dfs(graph, neighbor, visited);
    }
}

Time: O(V + E) | Space: O(V)

---

DFS — Iterative

function dfsIterative(graph, start) {
    const visited = new Set();
    const stack   = [start];
    const result  = [];
    while (stack.length) {
        const node = stack.pop();
        if (visited.has(node)) continue;
        visited.add(node);
        result.push(node);
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) stack.push(neighbor);
        }
    }
    return result;
}

---

Cycle Detection (Directed Graph)

Three-color DFS: white=0 (unvisited), gray=1 (in-stack), black=2 (done).

function hasCycle(graph, n) {
    const color = new Array(n).fill(0);
    function dfs(v) {
        color[v] = 1; // gray
        for (const u of graph[v]) {
            if (color[u] === 1) return true;  // back edge
            if (color[u] === 0 && dfs(u)) return true;
        }
        color[v] = 2; // black
        return false;
    }
    for (let i = 0; i < n; i++) {
        if (color[i] === 0 && dfs(i)) return true;
    }
    return false;
}

---

Topological Sort (Kahn's BFS)

function topoSort(n, edges) {
    const graph    = Array.from({ length: n }, () => []);
    const indegree = new Array(n).fill(0);
    for (const [u, v] of edges) { graph[u].push(v); indegree[v]++; }

    const queue = [];
    for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);

    const order = [];
    while (queue.length) {
        const node = queue.shift();
        order.push(node);
        for (const nb of graph[node]) {
            if (--indegree[nb] === 0) queue.push(nb);
        }
    }
    return order.length === n ? order : []; // empty = cycle
}

Time: O(V + E) | Space: O(V)

---

Grid BFS — Island / Flood Fill Pattern

function numIslands(grid) {
    const R = grid.length, C = grid[0].length;
    let count = 0;
    function dfs(r, c) {
        if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] !== '1') return;
        grid[r][c] = '0';
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1);
    }
    for (let r = 0; r < R; r++)
        for (let c = 0; c < C; c++)
            if (grid[r][c] === '1') { dfs(r, c); count++; }
    return count;
}

Time: O(R × C) | Space: O(R × C)

---

Multi-source BFS

function multiSourceBFS(grid) {
    const R = grid.length, C = grid[0].length;
    const queue = [];
    // Enqueue all sources
    for (let r = 0; r < R; r++)
        for (let c = 0; c < C; c++)
            if (grid[r][c] === 0) queue.push([r, c, 0]);

    const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
    while (queue.length) {
        const [r, c, d] = queue.shift();
        for (const [dr, dc] of dirs) {
            const nr = r+dr, nc = c+dc;
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] === 1) {
                grid[nr][nc] = d + 1; queue.push([nr, nc, d + 1]);
            }
        }
    }
}