Graphs, BFS and DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25// The graph:  A → B, A → C, B → D, C → D, D → A
const edges = [['A','B'], ['A','C'], ['B','D'], ['C','D'], ['D','A']];

// 1. EDGE LIST. Compact, but answering "who are A's neighbours" is O(E).
console.log('edge list:', edges);

// 2. ADJACENCY LIST. The default choice: O(V + E) space, O(1) to get neighbours.
const adjacency = new Map();
for (const [from, to] of edges) {
  if (!adjacency.has(from)) adjacency.set(from, []);
  adjacency.get(from).push(to);
}
console.log('adjacency list:', [...adjacency]);
console.log("A's neighbours:", adjacency.get('A'));

// 3. ADJACENCY MATRIX. O(V^2) space, O(1) to ask "is there an edge a→b".
const nodes = ['A', 'B', 'C', 'D'];
const index = new Map(nodes.map((n, i) => [n, i]));
const matrix = nodes.map(() => new Array(nodes.length).fill(0));
for (const [from, to] of edges) matrix[index.get(from)][index.get(to)] = 1;

console.log('adjacency matrix:');
console.log('    ' + nodes.join(' '));
matrix.forEach((row, i) => console.log(nodes[i] + '   ' + row.join(' ')));
console.log('is there an edge A→D?', matrix[index.get('A')][index.get('D')] === 1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// Interviews give you edges as an array of pairs. Undirected means add both ways.
function buildGraph(n, edgeList, directed = false) {
  const g = new Map();
  for (let i = 0; i < n; i++) g.set(i, []);       // include isolated nodes
  for (const [a, b] of edgeList) {
    g.get(a).push(b);
    if (!directed) g.get(b).push(a);
  }
  return g;
}

const undirected = buildGraph(5, [[0,1],[0,2],[1,3],[3,4]]);
console.log('undirected:', [...undirected]);
console.log('node 0 neighbours:', undirected.get(0), '| node 3:', undirected.get(3));

const directed = buildGraph(4, [[0,1],[1,2],[2,3]], true);
console.log('directed:', [...directed]);
console.log('node 3 has no outgoing edges:', directed.get(3));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33const graph = new Map([
  [0, [1, 2]],
  [1, [0, 3]],
  [2, [0, 3]],
  [3, [1, 2, 4]],
  [4, [3]],
]);

function dfsRecursive(start, graph, visited = new Set(), order = []) {
  if (visited.has(start)) return order;      // the only difference from a tree
  visited.add(start);
  order.push(start);
  for (const next of graph.get(start)) dfsRecursive(next, graph, visited, order);
  return order;
}

function dfsIterative(start, graph) {
  const visited = new Set();
  const order = [];
  const stack = [start];
  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    // Push in reverse so the first neighbour is explored first.
    for (let i = graph.get(node).length - 1; i >= 0; i--) stack.push(graph.get(node)[i]);
  }
  return order;
}

console.log('DFS recursive:', dfsRecursive(0, graph));
console.log('DFS iterative:', dfsIterative(0, graph));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39const graph = new Map([
  [0, [1, 2]],
  [1, [0, 3]],
  [2, [0, 3]],
  [3, [1, 2, 4]],
  [4, [3]],
]);

function bfs(start, graph) {
  const visited = new Set([start]);
  const distance = new Map([[start, 0]]);
  const parent = new Map([[start, null]]);
  const queue = [start];
  let head = 0;                                 // head pointer, never shift

  while (head < queue.length) {
    const node = queue[head++];
    for (const next of graph.get(node)) {
      if (visited.has(next)) continue;
      visited.add(next);                        // mark on ENQUEUE
      distance.set(next, distance.get(node) + 1);
      parent.set(next, node);
      queue.push(next);
    }
  }
  return { order: queue, distance, parent };
}

const result = bfs(0, graph);
console.log('BFS order:', result.order);
console.log('distances from 0:', [...result.distance]);

// Rebuild the actual shortest path by walking parents backwards.
function pathTo(target, parent) {
  const path = [];
  for (let n = target; n !== null && n !== undefined; n = parent.get(n)) path.push(n);
  return path.reverse();
}
console.log('shortest path 0 → 4:', pathTo(4, result.parent));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27const graph = new Map([[ 'A', ['B','C'] ], [ 'B', ['D'] ], [ 'C', ['D','E'] ], [ 'D', ['F'] ], [ 'E', ['F'] ], [ 'F', [] ]]);

function shortestPath(start, goal, graph) {
  if (start === goal) return [start];
  const parent = new Map([[start, null]]);
  const queue = [start];
  let head = 0;

  while (head < queue.length) {
    const node = queue[head++];
    for (const next of graph.get(node) ?? []) {
      if (parent.has(next)) continue;           // parent map doubles as visited
      parent.set(next, node);
      if (next === goal) {
        const path = [];
        for (let n = goal; n !== null; n = parent.get(n)) path.push(n);
        return path.reverse();
      }
      queue.push(next);
    }
  }
  return null;                                   // unreachable
}

console.log('A → F:', shortestPath('A', 'F', graph));
console.log('A → A:', shortestPath('A', 'A', graph));
console.log('F → A:', shortestPath('F', 'A', graph), '← no path, directed graph');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28function countComponents(n, edgeList) {
  const g = new Map();
  for (let i = 0; i < n; i++) g.set(i, []);
  for (const [a, b] of edgeList) { g.get(a).push(b); g.get(b).push(a); }

  const visited = new Set();
  const components = [];

  for (let start = 0; start < n; start++) {
    if (visited.has(start)) continue;
    // A new component begins here.
    const group = [];
    const stack = [start];
    while (stack.length) {
      const node = stack.pop();
      if (visited.has(node)) continue;
      visited.add(node);
      group.push(node);
      for (const next of g.get(node)) if (!visited.has(next)) stack.push(next);
    }
    components.push(group.sort((a, b) => a - b));
  }
  return { count: components.length, components };
}

console.log(countComponents(5, [[0,1],[1,2],[3,4]]));
console.log(countComponents(4, []), '← no edges: every node is its own component');
console.log(countComponents(3, [[0,1],[1,2],[0,2]]), '← one component with a cycle');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37function countIslands(grid) {
  if (grid.length === 0) return 0;
  const rows = grid.length, cols = grid[0].length;
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  // The four directions, written once. Diagonals would add four more pairs.
  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  let islands = 0;

  const flood = (r, c) => {
    const stack = [[r, c]];
    while (stack.length) {
      const [y, x] = stack.pop();
      // Bounds check FIRST, then the seen check, then the land check.
      if (y < 0 || y >= rows || x < 0 || x >= cols) continue;
      if (seen[y][x] || grid[y][x] !== '1') continue;
      seen[y][x] = true;
      for (const [dy, dx] of DIRS) stack.push([y + dy, x + dx]);
    }
  };

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1' && !seen[r][c]) { islands++; flood(r, c); }
    }
  }
  return islands;
}

console.log(countIslands([
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1'],
]));   // 3

console.log(countIslands([['1','1','1'],['0','1','0'],['1','1','1']]));   // 1
console.log(countIslands([['0']]));                                        // 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28function shortestGridPath(grid) {
  const rows = grid.length, cols = grid[0].length;
  if (grid[0][0] === 1 || grid[rows-1][cols-1] === 1) return -1;

  const DIRS = [[-1,0],[1,0],[0,-1],[0,1]];
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const queue = [[0, 0, 1]];        // row, col, steps taken
  let head = 0;
  seen[0][0] = true;

  while (head < queue.length) {
    const [r, c, steps] = queue[head++];
    if (r === rows - 1 && c === cols - 1) return steps;

    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (seen[nr][nc] || grid[nr][nc] === 1) continue;
      seen[nr][nc] = true;
      queue.push([nr, nc, steps + 1]);
    }
  }
  return -1;
}

console.log(shortestGridPath([[0,0,0],[1,1,0],[1,1,0]]));   // 5
console.log(shortestGridPath([[0,1],[1,0]]));               // -1, blocked
console.log(shortestGridPath([[0]]));                        // 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24function hasCycleUndirected(n, edgeList) {
  const g = new Map();
  for (let i = 0; i < n; i++) g.set(i, []);
  for (const [a, b] of edgeList) { g.get(a).push(b); g.get(b).push(a); }

  const visited = new Set();

  const dfs = (node, parent) => {
    visited.add(node);
    for (const next of g.get(node)) {
      if (next === parent) continue;            // the edge we arrived on
      if (visited.has(next)) return true;       // a different way back: cycle
      if (dfs(next, node)) return true;
    }
    return false;
  };

  for (let i = 0; i < n; i++) if (!visited.has(i) && dfs(i, -1)) return true;
  return false;
}

console.log('tree (0-1, 1-2):', hasCycleUndirected(3, [[0,1],[1,2]]));           // false
console.log('triangle:        ', hasCycleUndirected(3, [[0,1],[1,2],[2,0]]));    // true
console.log('two components:  ', hasCycleUndirected(5, [[0,1],[2,3],[3,4],[4,2]])); // true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25function hasCycleDirected(n, edgeList) {
  const g = new Map();
  for (let i = 0; i < n; i++) g.set(i, []);
  for (const [a, b] of edgeList) g.get(a).push(b);

  // 0 = unvisited, 1 = in progress on the current path, 2 = finished
  const state = new Array(n).fill(0);

  const dfs = (node) => {
    if (state[node] === 1) return true;      // back edge: cycle
    if (state[node] === 2) return false;     // already fully explored, fine
    state[node] = 1;
    for (const next of g.get(node)) if (dfs(next)) return true;
    state[node] = 2;                          // done with this node
    return false;
  };

  for (let i = 0; i < n; i++) if (dfs(i)) return true;
  return false;
}

console.log('chain 0→1→2:      ', hasCycleDirected(3, [[0,1],[1,2]]));            // false
console.log('cycle 0→1→2→0:    ', hasCycleDirected(3, [[0,1],[1,2],[2,0]]));      // true
console.log('diamond, no cycle:', hasCycleDirected(4, [[0,1],[0,2],[1,3],[2,3]])); // false
console.log('self loop:        ', hasCycleDirected(1, [[0,0]]));                   // true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28// Can the nodes be split into two groups with no edge inside a group?
// BFS, colouring each neighbour the opposite colour. A conflict means no.
function isBipartite(n, edgeList) {
  const g = new Map();
  for (let i = 0; i < n; i++) g.set(i, []);
  for (const [a, b] of edgeList) { g.get(a).push(b); g.get(b).push(a); }

  const colour = new Array(n).fill(0);       // 0 = uncoloured, 1 and -1 = the groups

  for (let start = 0; start < n; start++) {
    if (colour[start] !== 0) continue;
    colour[start] = 1;
    const queue = [start];
    let head = 0;
    while (head < queue.length) {
      const node = queue[head++];
      for (const next of g.get(node)) {
        if (colour[next] === colour[node]) return false;    // same group: conflict
        if (colour[next] === 0) { colour[next] = -colour[node]; queue.push(next); }
      }
    }
  }
  return true;
}

console.log('square (4-cycle):  ', isBipartite(4, [[0,1],[1,2],[2,3],[3,0]]));    // true
console.log('triangle (3-cycle):', isBipartite(3, [[0,1],[1,2],[2,0]]));          // false
console.log('a tree:            ', isBipartite(3, [[0,1],[1,2]]));                // true