Graphs

A graph is a set of nodes (vertices) connected by edges. Graphs model relationships that trees cannot: friend networks, road maps, dependency chains, and web links. Unlike trees, graphs can have cycles and multiple paths between nodes.

Representations

Choose adjacency lists for sparse graphs (most real-world cases) and adjacency matrices for dense graphs or when O(1) edge lookup is critical.

// Adjacency list — space: O(V + E)
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C'],
};

// Weighted adjacency list
const weighted = {
  A: [['B', 4], ['C', 2]],
  B: [['A', 4], ['D', 1]],
  C: [['A', 2], ['D', 5]],
  D: [['B', 1], ['C', 5]],
};

Breadth-First Search (BFS)

BFS explores all neighbours at the current depth before moving deeper. Use it to find the shortest path in an unweighted graph or to process nodes level by level.

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

  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const neighbour of graph[node]) {
      if (!visited.has(neighbour)) {
        visited.add(neighbour);
        queue.push(neighbour);
      }
    }
  }
  return order;
}

// Shortest path (unweighted)
function shortestPath(graph, start, end) {
  const queue = [[start, [start]]];
  const visited = new Set([start]);
  while (queue.length) {
    const [node, path] = queue.shift();
    if (node === end) return path;
    for (const n of graph[node]) {
      if (!visited.has(n)) { visited.add(n); queue.push([n, [...path, n]]); }
    }
  }
  return null;
}

Depth-First Search (DFS)

DFS goes as deep as possible before backtracking. Use it for cycle detection, topological sort, connected components, and maze solving.

// Recursive DFS
function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  console.log(node);
  for (const neighbour of graph[node]) {
    dfs(graph, neighbour, visited);
  }
}

// Detect cycle in directed graph
function hasCycle(graph) {
  const visited = new Set();
  const inStack = new Set();

  function dfsCheck(node) {
    visited.add(node);
    inStack.add(node);
    for (const n of graph[node] || []) {
      if (!visited.has(n) && dfsCheck(n)) return true;
      if (inStack.has(n)) return true;
    }
    inStack.delete(node);
    return false;
  }

  return Object.keys(graph).some(n => !visited.has(n) && dfsCheck(n));
}

Topological Sort

Topological sort orders nodes of a Directed Acyclic Graph (DAG) so that every edge points forward. Useful for dependency resolution and build systems.

function topoSort(graph) {
  const visited = new Set();
  const stack = [];

  function dfs(node) {
    visited.add(node);
    for (const n of graph[node] || []) {
      if (!visited.has(n)) dfs(n);
    }
    stack.push(node); // push after all descendants
  }

  for (const node of Object.keys(graph)) {
    if (!visited.has(node)) dfs(node);
  }
  return stack.reverse();
}

Complexity

• BFS / DFS: O(V + E) time, O(V) space
• Adjacency list: O(V + E) space
• Adjacency matrix: O(V²) space, O(1) edge check