Graphs: The Complete Interview Guide

// Raw input from Google (edge list)
const edges = [
  [0, 1],
  [1, 2],
  [2, 0],
  [3, 4]
];

// Adjacency list: Map<node, array of neighbors>
const graph = new Map([
  [0, [1, 2]],    // Node 0 connects to 1 and 2
  [1, [0, 2]],    // Node 1 connects to 0 and 2
  [2, [0, 1]],    // Node 2 connects to 0 and 1
  [3, [4]],       // Node 3 connects to 4
  [4, [3]]        // Node 4 connects to 3
]);

function buildAdjacencyListUndirected(edges, numNodes) {
  const graph = new Map();

  // Initialize empty adjacency lists for all nodes
  for (let i = 0; i < numNodes; i++) {
    graph.set(i, []);
  }

  // Add edges
  for (const [u, v] of edges) {
    graph.get(u).push(v);
    graph.get(v).push(u);  // Add reverse edge for undirected
  }

  return graph;
}

const graph = buildAdjacencyListUndirected([[0, 1], [1, 2], [2, 0], [3, 4]], 5);
// Result: Map { 0 => [1, 2], 1 => [0, 2], 2 => [1, 0], 3 => [4], 4 => [3] }

function buildAdjacencyListDirected(edges, numNodes) {
  const graph = new Map();

  for (let i = 0; i < numNodes; i++) {
    graph.set(i, []);
  }

  for (const [u, v] of edges) {
    graph.get(u).push(v);  // Only u -> v, no reverse edge
  }

  return graph;
}

graph = Map {
  0 => [1, 2]      <-- Array with 2 elements
  1 => [0, 2]      <-- Array with 2 elements
  2 => [1, 0]      <-- Array with 2 elements
  3 => [4]         <-- Array with 1 element
  4 => [3]         <-- Array with 1 element
}

Space used: O(V + E)
  V = number of entries in the map
  E = total elements across all arrays

const edges = [[0,1], [0,2], [1,3], [2,3], [3,4], [4,5], [2,5]];
const graph = buildAdjacencyListUndirected(edges, 6);

// To find neighbors of node 3:
const neighbors = graph.get(3);  // [1, 2, 4] — O(1) access!

// To iterate all edges:
for (const [node, neighbors] of graph) {
  for (const neighbor of neighbors) {
    // Process edge node -> neighbor
  }
}
// This is O(V + E) — very efficient

// Adjacency matrix for undirected graph
//     0  1  2  3  4
const matrix = [
  [0, 1, 1, 0, 0],  // Node 0 connects to 1, 2
  [1, 0, 1, 0, 0],  // Node 1 connects to 0, 2
  [1, 1, 0, 1, 1],  // Node 2 connects to 0, 1, 3, 4
  [0, 0, 1, 0, 0],  // Node 3 connects to 2
  [0, 0, 1, 0, 0]   // Node 4 connects to 2
];

// matrix[u][v] = 1 if edge u->v exists, 0 otherwise
// To check if 0→1 exists: matrix[0][1] === 1  // O(1)!

function buildAdjacencyMatrix(edges, numNodes) {
  // Create V×V matrix filled with 0s
  const matrix = Array(numNodes)
    .fill(0)
    .map(() => Array(numNodes).fill(0));

  // Add edges
  for (const [u, v] of edges) {
    matrix[u][v] = 1;
    matrix[v][u] = 1;  // For undirected graphs
  }

  return matrix;
}

matrix = [
  [0, 1, 1, 0, 0]
  [1, 0, 1, 0, 0]
  [1, 1, 0, 1, 1]
  [0, 0, 1, 0, 0]
  [0, 0, 1, 0, 0]
]

Space used: O(V²) — always, regardless of number of edges!

// Every node connects to every other node
const edges = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]];
const matrix = buildAdjacencyMatrix(edges, 5);

// Quick check: do nodes 2 and 4 connect?
const exists = matrix[2][4] === 1;  // O(1)

// But if V = 10,000, matrix needs 10,000 × 10,000 = 100 million cells!
// Even if only 100 edges exist. Wasteful.

// Grid input (example: island matrix)
const grid = [
  ['1', '1', '0', '0'],
  ['1', '1', '0', '1'],
  ['0', '0', '1', '0']
];

// This IS a graph. No need to build an adjacency list!
// Each cell is a node. Adjacent cells are connected.
// The grid itself IS the representation.

// WRONG: Don't do this for grids!
const graph = new Map();
for (let r = 0; r < rows; r++) {
  for (let c = 0; c < cols; c++) {
    graph.set([r, c], []); // Build adjacency list from grid
  }
}
// This is extra work and memory.

// CORRECT: The grid IS the graph. Use directions array.
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];  // right, left, down, up

// To find neighbors of cell (r, c):
function getNeighbors(r, c, grid) {
  const neighbors = [];
  for (const [dr, dc] of directions) {
    const nr = r + dr;
    const nc = c + dc;
    if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length) {
      neighbors.push([nr, nc]);
    }
  }
  return neighbors;
}

getNeighbors(0, 0, grid);  // [[0, 1], [1, 0]] (right and down are in bounds)

grid = [
  ['1', '1', '0', '0']
  ['1', '1', '0', '1']
  ['0', '0', '1', '0']
]

Space used: O(rows × cols) — the grid itself, no extra structure

Neighbors of (1, 1):
  - Up:    (0, 1) ✓
  - Down:  (2, 1) ✓
  - Left:  (1, 0) ✓
  - Right: (1, 2) ✓

// 4-directional (cardinal): up, down, left, right
const directions4 = [[0, 1], [0, -1], [1, 0], [-1, 0]];

// 8-directional (including diagonals)
const directions8 = [
  [0, 1], [0, -1], [1, 0], [-1, 0],  // Cardinal
  [1, 1], [1, -1], [-1, 1], [-1, -1]  // Diagonals
];

Imagine you're in a maze and want to find the shortest exit:
1. Start at your position (enqueue)
2. Check all adjacent cells (neighbors)
3. Mark them as visited and enqueue them
4. Dequeue the next cell and repeat
5. First time you reach the exit? That's the shortest path.

Why? Because you explore all cells at distance 1 before distance 2, etc.

function bfs(startNode, graph) {
  const queue = [startNode];
  const visited = new Set([startNode]);

  while (queue.length > 0) {
    const current = queue.shift();  // Dequeue from front

    // Process current node
    console.log(current);

    // Enqueue all unvisited neighbors
    for (const neighbor of graph.get(current)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);  // Enqueue at back
      }
    }
  }
}

// Graph as adjacency list
const graph = new Map([
  [0, [1, 2]],
  [1, [0, 3]],
  [2, [0, 3]],
  [3, [1, 2]]
]);

function bfsAdjacencyList(startNode, graph) {
  const queue = [startNode];
  const visited = new Set([startNode]);
  const result = [];

  while (queue.length > 0) {
    const current = queue.shift();
    result.push(current);

    for (const neighbor of graph.get(current)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}

bfsAdjacencyList(0, graph);  // [0, 1, 2, 3]

function bfsGrid(grid, startRow, startCol) {
  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  const queue = [[startRow, startCol]];
  const visited = new Set();
  visited.add(`${startRow},${startCol}`);
  const result = [];

  while (queue.length > 0) {
    const [r, c] = queue.shift();
    result.push([r, c]);

    // Check all 4 neighbors
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      const key = `${nr},${nc}`;

      // In bounds and not visited?
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited.has(key)) {
        visited.add(key);
        queue.push([nr, nc]);
      }
    }
  }

  return result;
}

const grid = [
  ['A', 'B', 'C'],
  ['D', 'E', 'F'],
  ['G', 'H', 'I']
];

bfsGrid(grid, 0, 0);
// [[0,0], [0,1], [1,0], [0,2], [1,1], [2,0], [1,2], [2,1], [2,2]]

Imagine exploring a cave system:
1. Go down one tunnel as far as possible
2. When you hit a dead end, backtrack
3. Take the next unexplored tunnel
4. Repeat until all reachable areas are explored

This is depth-first exploration.

function dfs(node, graph, visited) {
  visited.add(node);
  console.log(node);

  for (const neighbor of graph.get(node)) {
    if (!visited.has(neighbor)) {
      dfs(neighbor, graph, visited);  // Recursive call = use the stack
    }
  }
}

const visited = new Set();
dfs(0, graph, visited);

function dfsAdjacencyList(startNode, graph) {
  const visited = new Set();
  const result = [];

  function dfsHelper(node) {
    visited.add(node);
    result.push(node);

    for (const neighbor of graph.get(node)) {
      if (!visited.has(neighbor)) {
        dfsHelper(neighbor);
      }
    }
  }

  dfsHelper(startNode);
  return result;
}

const graph = new Map([
  [0, [1, 2]],
  [1, [0, 3]],
  [2, [0, 3]],
  [3, [1, 2]]
]);

dfsAdjacencyList(0, graph);  // [0, 1, 3, 2] or similar (order may vary)

function dfsGrid(grid, startRow, startCol, visited) {
  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  function dfsHelper(r, c) {
    visited.add(`${r},${c}`);

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      const key = `${nr},${nc}`;

      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited.has(key)) {
        dfsHelper(nr, nc);
      }
    }
  }

  dfsHelper(startRow, startCol);
}

// Usage:
const grid = [
  ['1', '1', '0'],
  ['0', '1', '0'],
  ['1', '1', '0']
];

const visited = new Set();
dfsGrid(grid, 0, 0, visited);
// visited now contains all reachable '1' cells from (0, 0)

function dfsIterative(startNode, graph) {
  const stack = [startNode];
  const visited = new Set([startNode]);
  const result = [];

  while (stack.length > 0) {
    const current = stack.pop();  // Pop from top of stack
    result.push(current);

    for (const neighbor of graph.get(current)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);  // Push to stack
      }
    }
  }

  return result;
}

Input:
[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Output: 3

Explanation:
  Island 1: the connected group of '1's in the top-left
  Island 2: the '1' in the middle
  Island 3: the connected group of '1's in the bottom-right

Initial grid:
  1 1 0 0 0
  1 1 0 0 0
  0 0 1 0 0
  0 0 0 1 1

Step 1: Find (0,0) = '1' → Start DFS from (0,0)
  DFS marks all connected '1's as '0' (or visited):
  X X 0 0 0
  X X 0 0 0
  0 0 1 0 0
  0 0 0 1 1

Island count: 1

Step 2: Continue scanning, find (2,2) = '1' → Start DFS from (2,2)
  X X 0 0 0
  X X 0 0 0
  0 0 X 0 0
  0 0 0 1 1

Island count: 2

Step 3: Continue scanning, find (3,3) = '1' → Start DFS from (3,3)
  X X 0 0 0
  X X 0 0 0
  0 0 X 0 0
  0 0 0 X X

Island count: 3

Final answer: 3 islands

function numIslandsDFS(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let islandCount = 0;

  const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  function dfs(r, c) {
    // Mark current cell as visited by changing it to '0'
    grid[r][c] = '0';

    // Explore all 4 neighbors
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;

      // If neighbor is in bounds and is land ('1'), visit it
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
        dfs(nr, nc);
      }
    }
  }

  // Scan every cell
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      // Found a new island
      if (grid[r][c] === '1') {
        dfs(r, c);  // Mark entire island as visited
        islandCount++;
      }
    }
  }

  return islandCount;
}

function numIslandsBFS(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let islandCount = 0;

  const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  function bfs(startRow, startCol) {
    const queue = [[startRow, startCol]];
    grid[startRow][startCol] = '0';  // Mark as visited

    while (queue.length > 0) {
      const [r, c] = queue.shift();

      // Check all 4 neighbors
      for (const [dr, dc] of directions) {
        const nr = r + dr;
        const nc = c + dc;

        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
          grid[nr][nc] = '0';  // Mark as visited immediately
          queue.push([nr, nc]);
        }
      }
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        bfs(r, c);
        islandCount++;
      }
    }
  }

  return islandCount;
}

Input:
[
  [1,1,0],
  [0,1,0],
  [1,0,1]
]

Output: 1

Explanation:
  We can flip (0,2) from 0 to 1, connecting the left island to the right island.

Initial:
  1 1 0
  0 1 0
  1 0 1

After flip:
  1 1 1
  0 1 0
  1 0 1

Now islands are connected.

Single-source BFS:
  Queue: [start_cell]
  Found shortest path when target is reached.

Multi-source BFS:
  Queue: [all_cells_of_island_1]
  Found shortest path when any cell of island_2 is reached.

Why? Because we're exploring from ALL cells of island 1 simultaneously,
and we stop when we first touch island 2. That's the shortest bridge.

Initial grid (1 = island, 0 = water):
  1 1 0
  0 1 0
  1 0 1

Step 1: DFS to find first island starting from (0,0):
  Mark all connected 1's: {(0,0), (0,1), (1,1)} form island 1

Step 2: Multi-source BFS from all cells of island 1:

  Distance 0 (initial queue):
    Queue: [(0,0), (0,1), (1,1)]
    These are cells of island 1

  Distance 1 (neighbors of island 1):
    From (0,0): neighbors are (0,1)✓ island 1, (1,0) = '0' → add distance 1
    From (0,1): neighbors are (0,0)✓, (0,2) = '0' → add distance 1, (1,1)✓
    From (1,1): neighbors are (0,1)✓, (1,0) = '0' → add distance 1, (1,2) = '0' → add distance 1, (2,1) = '0' → add distance 1

    New frontier at distance 1: [(1,0), (0,2), (1,2), (2,1)]

  Distance 2 (neighbors at distance 1):
    From (0,2): neighbors are (0,1)✓, (1,2) already have = '0'
    From (1,0): neighbors are (0,0)✓, (1,1)✓, (2,0) = '1' ← THIS IS ISLAND 2!

    Found island 2 at distance 2!
    Return 2 - 1 = 1 (we need to flip 1 cell, which is (0,2) or (1,0) or (1,2) or (2,1))

Actually, shortest bridge is 1 because we can flip (0,2) to connect directly.
The algorithm finds the minimum distance as 2 flips, but the answer is 1.
Let me reconsider...

Actually: the grid shows distance to the NEAREST other-island cell.
Distance 0 = island 1 cells
Distance 1 = water cells 1 step from island 1
Distance 2 = water cells 2 steps from island 1
etc.

When we hit a water cell that's 1 step from island 2, that's the bridge!

Let me redo:

Initial:
  1 1 0
  0 1 0
  1 0 1

Island 1: {(0,0), (0,1), (1,1)}
Island 2: {(2,0), (2,2)}

Multi-source BFS from island 1:
  Start: queue = [(0,0), (0,1), (1,1)], distance[island1] = 0

  Iteration 1: Process all cells at distance 0
    (0,0): neighbors (0,1)✓island1, (1,0)='0'→add distance 1, (−1,0)✗
    (0,1): neighbors (0,0)✓, (0,2)='0'→add distance 1, (1,1)✓
    (1,1): neighbors (0,1)✓, (1,0)='0'(already seen), (1,2)='0'→add distance 1, (2,1)='0'→add distance 1

  Iteration 2: Process cells at distance 1: (1,0), (0,2), (1,2), (2,1)
    (1,0): neighbors (0,0)✓, (1,1)✓, (2,0)='1'→ISLAND 2 FOUND! Distance 2

  Return 2 - 1 = 1

function shortestBridge(grid) {
  const n = grid.length;
  const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  // Step 1: Find the first island using DFS
  let firstIslandFound = false;
  const firstIsland = [];

  function dfs(r, c) {
    grid[r][c] = 2;  // Mark as visited/island 1
    firstIsland.push([r, c]);

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 1) {
        dfs(nr, nc);
      }
    }
  }

  // Find first island
  outerLoop: for (let r = 0; r < n && !firstIslandFound; r++) {
    for (let c = 0; c < n && !firstIslandFound; c++) {
      if (grid[r][c] === 1) {
        dfs(r, c);
        firstIslandFound = true;
      }
    }
  }

  // Step 2: Multi-source BFS from the first island
  const queue = [];

  // Initialize queue with all cells of the first island
  for (const [r, c] of firstIsland) {
    queue.push([r, c, 0]);  // [row, col, distance]
  }

  const visited = new Set();
  for (const [r, c] of firstIsland) {
    visited.add(`${r},${c}`);
  }

  // BFS
  while (queue.length > 0) {
    const [r, c, distance] = queue.shift();

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      const key = `${nr},${nc}`;

      if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited.has(key)) {
        visited.add(key);

        // Found a cell of the second island
        if (grid[nr][nc] === 1) {
          return distance;  // Distance is number of 0s to flip
        }

        // Enqueue water cell (grid[nr][nc] === 0)
        queue.push([nr, nc, distance + 1]);
      }
    }
  }

  return -1;  // Should never reach here if exactly 2 islands exist
}

function cloneGraph(node) {
  if (!node) return null;

  const visited = new Map();  // old_node → new_node

  function dfs(oldNode) {
    if (visited.has(oldNode)) {
      return visited.get(oldNode);
    }

    const newNode = new Node(oldNode.val);
    visited.set(oldNode, newNode);

    for (const neighbor of oldNode.neighbors) {
      newNode.neighbors.push(dfs(neighbor));
    }

    return newNode;
  }

  return dfs(node);
}

function canFinish(numCourses, prerequisites) {
  // Build adjacency list and in-degree array
  const graph = new Map();
  const inDegree = new Array(numCourses).fill(0);

  for (let i = 0; i < numCourses; i++) {
    graph.set(i, []);
  }

  for (const [course, prereq] of prerequisites) {
    graph.get(prereq).push(course);  // prereq → course
    inDegree[course]++;
  }

  // Kahn's algorithm: topological sort
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }

  let processedCount = 0;

  while (queue.length > 0) {
    const course = queue.shift();
    processedCount++;

    for (const nextCourse of graph.get(course)) {
      inDegree[nextCourse]--;
      if (inDegree[nextCourse] === 0) {
        queue.push(nextCourse);
      }
    }
  }

  return processedCount === numCourses;  // true if no cycle, false if cycle
}

Graph:
  A --5--> B --1--> C
  A --2--> C

BFS from A:
  Distance to C via B: 5 + 1 = 6
  Distance to C direct: 2

  But BFS might find B first (distance 1), then through B to C (distance 6),
  missing the direct shorter path of 2.

Dijkstra solves this by always processing the closest unvisited node next.

function dijkstra(graph, start) {
  const distances = new Map();
  const visited = new Set();
  const pq = new MinHeap();  // Min-heap: (distance, node)

  // Initialize distances
  for (const node of graph.keys()) {
    distances.set(node, Infinity);
  }
  distances.set(start, 0);
  pq.push([0, start]);

  while (!pq.isEmpty()) {
    const [dist, node] = pq.pop();

    if (visited.has(node)) continue;
    visited.add(node);

    // Relax edges
    for (const [neighbor, weight] of graph.get(node)) {
      const newDist = dist + weight;
      if (newDist < distances.get(neighbor)) {
        distances.set(neighbor, newDist);
        pq.push([newDist, neighbor]);
      }
    }
  }

  return distances;
}