Graphs

Graphs generalize trees: nodes can have any number of connections, cycles are allowed, and edges can be directed or weighted. Many real-world problems -- social networks, routing, dependency resolution -- are graph problems in disguise.

Representations

Adjacency List (Preferred for Most Problems)

// Unweighted graph
type Graph = Map<number, number[]>;

function buildGraph(edges: [number, number][]): Graph {
  const graph: Graph = new Map();
  for (const [u, v] of edges) {
    if (!graph.has(u)) graph.set(u, []);
    if (!graph.has(v)) graph.set(v, []);
    graph.get(u)!.push(v);
    graph.get(v)!.push(u); // remove for directed graph
  }
  return graph;
}

// Weighted graph
type WeightedGraph = Map<number, [number, number][]>; // node -> [neighbor, weight]

Adjacency Matrix

// matrix[i][j] = 1 means edge from i to j
const matrix: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));

	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V^2)
Check edge exists	O(degree)	O(1)
Get all neighbors	O(degree)	O(V)
Best for	Sparse graphs	Dense graphs, quick edge lookup

Default to adjacency list. Most interview graphs are sparse.

BFS on Graphs

function bfs(graph: Graph, start: number): number[] {
  const visited = new Set<number>([start]);
  const queue: number[] = [start];
  const order: number[] = [];

  while (queue.length > 0) {
    const node = queue.shift()!;
    order.push(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return order;
}

BFS gives shortest path in unweighted graphs. To track distance:

function shortestPath(graph: Graph, start: number, end: number): number {
  const visited = new Set<number>([start]);
  const queue: [number, number][] = [[start, 0]]; // [node, distance]

  while (queue.length > 0) {
    const [node, dist] = queue.shift()!;
    if (node === end) return dist;

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }

  return -1; // unreachable
}

DFS on Graphs

function dfs(graph: Graph, start: number): number[] {
  const visited = new Set<number>();
  const order: number[] = [];

  function explore(node: number): void {
    visited.add(node);
    order.push(node);
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        explore(neighbor);
      }
    }
  }

  explore(start);
  return order;
}

Cycle Detection

Undirected Graph

function hasCycleUndirected(graph: Graph): boolean {
  const visited = new Set<number>();

  function dfs(node: number, parent: number): boolean {
    visited.add(node);
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) return true;
      } else if (neighbor !== parent) {
        return true; // back edge found
      }
    }
    return false;
  }

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      if (dfs(node, -1)) return true;
    }
  }
  return false;
}

Directed Graph (Three-Color DFS)

function hasCycleDirected(graph: Graph): boolean {
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Map<number, number>();

  for (const node of graph.keys()) color.set(node, WHITE);

  function dfs(node: number): boolean {
    color.set(node, GRAY);
    for (const neighbor of graph.get(node) ?? []) {
      if (color.get(neighbor) === GRAY) return true;  // back edge = cycle
      if (color.get(neighbor) === WHITE && dfs(neighbor)) return true;
    }
    color.set(node, BLACK);
    return false;
  }

  for (const node of graph.keys()) {
    if (color.get(node) === WHITE && dfs(node)) return true;
  }
  return false;
}

Topological Sort

Order nodes so that for every directed edge u -> v, u comes before v. Only possible in DAGs (directed acyclic graphs).

Kahn's Algorithm (BFS-based)

function topologicalSort(graph: Graph, numNodes: number): number[] {
  const inDegree = new Array(numNodes).fill(0);
  for (const [, neighbors] of graph) {
    for (const n of neighbors) inDegree[n]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < numNodes; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order: number[] = [];
  while (queue.length > 0) {
    const node = queue.shift()!;
    order.push(node);
    for (const neighbor of graph.get(node) ?? []) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  // If order.length < numNodes, there is a cycle
  return order.length === numNodes ? order : [];
}

Use cases: Build systems, course scheduling, dependency resolution.

Shortest Path Algorithms

Dijkstra's Algorithm

For graphs with non-negative edge weights.

function dijkstra(graph: WeightedGraph, start: number, n: number): number[] {
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;

  // Simple priority queue using sorted array (use a real heap in production)
  const pq: [number, number][] = [[0, start]]; // [distance, node]

  while (pq.length > 0) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift()!;

    if (d > dist[u]) continue; // stale entry

    for (const [v, weight] of graph.get(u) ?? []) {
      const newDist = dist[u] + weight;
      if (newDist < dist[v]) {
        dist[v] = newDist;
        pq.push([newDist, v]);
      }
    }
  }

  return dist;
}
// Time: O((V + E) log V) with proper heap

Bellman-Ford Algorithm

Handles negative edge weights. Detects negative cycles.

function bellmanFord(
  edges: [number, number, number][], // [from, to, weight]
  n: number,
  start: number
): number[] | null {
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;

  // Relax all edges V-1 times
  for (let i = 0; i < n - 1; i++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // Check for negative cycles
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      return null; // negative cycle exists
    }
  }

  return dist;
}
// Time: O(V * E)

Union-Find (Disjoint Set Union)

Efficiently tracks connected components. Two operations: find (which set?) and union (merge sets).

class UnionFind {
  parent: number[];
  rank: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }

  union(x: number, y: number): boolean {
    const px = this.find(x);
    const py = this.find(y);
    if (px === py) return false; // already connected

    // union by rank
    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else {
      this.parent[py] = px;
      this.rank[px]++;
    }
    return true;
  }

  connected(x: number, y: number): boolean {
    return this.find(x) === this.find(y);
  }
}
// Both operations: amortized O(α(n)) ≈ O(1)

Use cases: Number of connected components, redundant connections, Kruskal's MST, accounts merge.

Key Takeaways

Default to adjacency list. Build it from edge list at the start of your solution.
BFS for shortest path in unweighted graphs. DFS for exhaustive exploration.
Topological sort whenever you see dependencies or ordering constraints on a DAG.
Dijkstra for weighted shortest path (non-negative). Bellman-Ford when negative weights exist.
Union-Find for connectivity. Faster than BFS/DFS when you need repeated connectivity queries.
Always track visited nodes. Forgetting this is the most common graph bug.

Graphs

On this page