Graph Algorithms

Topological sort prerequisites

Topological sort orders the nodes of a directed acyclic graph (DAG) so that for every directed edge from node u to node v, u appears before v in the ordering.

Three conditions must all hold before you can apply topo sort:

1. The graph must be directed — edges have a direction.
2. The graph must be acyclic — no path leads back to itself.
3. You need an ordering of nodes that respects all directed dependencies.

Real-world examples: package dependency installation, build system task ordering, course prerequisite scheduling, spreadsheet cell evaluation.

Cycle → no valid order. If a cycle exists, at least one node in the cycle depends on itself (transitively), making it impossible to place all nodes in a valid linear order. Both topo sort algorithms detect this.

Kahn’s algorithm — BFS-based

Idea: Nodes with in-degree 0 have no prerequisites — they can go first. Process them, decrement their neighbors’ in-degrees, and enqueue any neighbor whose in-degree drops to 0. If you process all n nodes, the graph is acyclic. If some nodes are never processed, they form a cycle.

function topoSortKahn(n: number, edges: [number, number][]): number[] {
  const adj: number[][] = Array.from({ length: n }, () => [])
  const inDegree = new Array(n).fill(0)

  for (const [u, v] of edges) {
    adj[u].push(v)
    inDegree[v]++
  }

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

  const result: number[] = []
  while (queue.length > 0) {
    const node = queue.shift()!
    result.push(node)
    for (const neighbor of adj[node]) {
      inDegree[neighbor]--
      if (inDegree[neighbor] === 0) queue.push(neighbor)
    }
  }

  // result.length < n means a cycle prevented some nodes from ever reaching in-degree 0
  return result.length === n ? result : []
}

Time: O(V + E) — every vertex and edge is visited exactly once. Space: O(V + E) — adjacency list plus in-degree array.

Cycle detection: if result.length < n, a cycle exists.

DFS-based topo sort

Idea: Run DFS on every unvisited node. After fully exploring all descendants of a node (postorder), push it onto a stack. Reversing the stack gives the topological order.

function topoSortDFS(n: number, edges: [number, number][]): number[] {
  const adj: number[][] = Array.from({ length: n }, () => [])
  for (const [u, v] of edges) adj[u].push(v)

  // 0 = unvisited, 1 = in-progress (back edge = cycle), 2 = fully done
  const state = new Array(n).fill(0)
  const stack: number[] = []
  let hasCycle = false

  function dfs(node: number): void {
    if (hasCycle) return
    state[node] = 1
    for (const neighbor of adj[node]) {
      if (state[neighbor] === 1) { hasCycle = true; return }  // back edge
      if (state[neighbor] === 0) dfs(neighbor)
    }
    state[node] = 2   // postorder: all descendants processed
    stack.push(node)
  }

  for (let i = 0; i < n; i++) {
    if (state[i] === 0) dfs(i)
  }

  return hasCycle ? [] : stack.reverse()
}

Time: O(V + E). Space: O(V + E) plus O(V) call stack depth.

Kahn’s vs DFS: Kahn’s is iterative and cycle detection is implicit (count check). DFS feels more natural for problems where you’re already doing a DFS traversal. Prefer Kahn’s in interviews — simpler to reason about.

Course Schedule — LC 207

Can you finish all n courses given prerequisite pairs [a, b] (must take b before a)?

This is exactly cycle detection in a directed graph. If the prerequisite graph has a cycle, some course can never be taken.

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const adj: number[][] = Array.from({ length: numCourses }, () => [])
  const inDegree = new Array(numCourses).fill(0)

  for (const [a, b] of prerequisites) {
    adj[b].push(a)   // b must come before a
    inDegree[a]++
  }

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

  let processed = 0
  while (queue.length > 0) {
    const node = queue.shift()!
    processed++
    for (const next of adj[node]) {
      if (--inDegree[next] === 0) queue.push(next)
    }
  }

  return processed === numCourses
}

Time: O(V + E) where V = numCourses, E = prerequisites.length.

Course Schedule II — LC 210

Return a valid course ordering, or [] if impossible (cycle exists).

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const adj: number[][] = Array.from({ length: numCourses }, () => [])
  const inDegree = new Array(numCourses).fill(0)

  for (const [a, b] of prerequisites) {
    adj[b].push(a)
    inDegree[a]++
  }

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

  const order: number[] = []
  while (queue.length > 0) {
    const node = queue.shift()!
    order.push(node)
    for (const next of adj[node]) {
      if (--inDegree[next] === 0) queue.push(next)
    }
  }

  return order.length === numCourses ? order : []
}

This is identical to LC 207 with the small addition of collecting the order. Pattern: build graph, Kahn’s, check count.

Alien Dictionary — LC 269

Given a list of words sorted in an alien language’s lexicographic order, derive the character ordering.

Strategy:

1. Compare adjacent words character by character. The first position where they differ gives you an ordering constraint: character c1 comes before c2.
2. Build a directed graph of these character constraints.
3. Topo sort the character graph. If a cycle exists, the input is invalid.

Edge case: if words[i] is longer than words[i+1] and words[i+1] is a prefix of words[i] (e.g., "abc" before "ab"), the ordering is invalid.

function alienOrder(words: string[]): string {
  // Adjacency list and tracking for all unique characters
  const adj = new Map<string, Set<string>>()
  for (const word of words) {
    for (const ch of word) {
      if (!adj.has(ch)) adj.set(ch, new Set())
    }
  }

  // Extract ordering constraints from adjacent word pairs
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1]
    const minLen = Math.min(w1.length, w2.length)
    if (w1.length > w2.length && w1.startsWith(w2)) return ""  // invalid
    for (let j = 0; j < minLen; j++) {
      if (w1[j] !== w2[j]) {
        adj.get(w1[j])!.add(w2[j])
        break  // only the first differing character gives ordering info
      }
    }
  }

  // Kahn's topo sort on character graph
  const inDegree = new Map<string, number>()
  for (const ch of adj.keys()) inDegree.set(ch, 0)
  for (const [, neighbors] of adj) {
    for (const nb of neighbors) {
      inDegree.set(nb, (inDegree.get(nb) ?? 0) + 1)
    }
  }

  const queue: string[] = []
  for (const [ch, deg] of inDegree) {
    if (deg === 0) queue.push(ch)
  }

  let result = ""
  while (queue.length > 0) {
    const ch = queue.shift()!
    result += ch
    for (const nb of adj.get(ch)!) {
      inDegree.set(nb, inDegree.get(nb)! - 1)
      if (inDegree.get(nb) === 0) queue.push(nb)
    }
  }

  return result.length === adj.size ? result : ""
}

Time: O(C) where C is the total number of characters across all words. Space: O(U²) in the worst case for U unique characters (every pair could have an ordering constraint).

Dijkstra’s algorithm

Single-source shortest path for graphs with non-negative edge weights. Uses a min-heap to always expand the currently closest unvisited node.

Core invariant: when a node is popped from the heap with distance d, d is the true shortest distance to that node — it cannot be improved further (assuming non-negative weights).

class MinHeap {
  private heap: [number, number][] = []  // [distance, node]

  push(val: [number, number]): void {
    this.heap.push(val)
    this.bubbleUp(this.heap.length - 1)
  }

  pop(): [number, number] | undefined {
    if (this.heap.length === 0) return undefined
    const top = this.heap[0]
    const last = this.heap.pop()!
    if (this.heap.length > 0) {
      this.heap[0] = last
      this.sinkDown(0)
    }
    return top
  }

  get size(): number { return this.heap.length }

  private bubbleUp(i: number): void {
    while (i > 0) {
      const parent = (i - 1) >> 1
      if (this.heap[parent][0] <= this.heap[i][0]) break
      ;[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]]
      i = parent
    }
  }

  private sinkDown(i: number): void {
    const n = this.heap.length
    while (true) {
      let smallest = i
      const l = 2 * i + 1, r = 2 * i + 2
      if (l < n && this.heap[l][0] < this.heap[smallest][0]) smallest = l
      if (r < n && this.heap[r][0] < this.heap[smallest][0]) smallest = r
      if (smallest === i) break
      ;[this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]]
      i = smallest
    }
  }
}

// adj[u] = [[v, weight], ...]
function dijkstra(n: number, adj: [number, number][][], src: number): number[] {
  const dist = new Array(n).fill(Infinity)
  dist[src] = 0
  const heap = new MinHeap()
  heap.push([0, src])

  while (heap.size > 0) {
    const [d, u] = heap.pop()!
    if (d > dist[u]) continue  // stale heap entry — skip

    for (const [v, w] of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w
        heap.push([dist[v], v])
      }
    }
  }

  return dist
}

Time: O((V + E) log V). Space: O(V + E).

The if (d > dist[u]) continue guard is essential. Without it, stale entries in the heap cause incorrect processing. The heap may contain an old [7, u] entry after a shorter path [3, u] was found — the guard skips the stale one.

Network Delay Time — LC 743

Signal starts at node k. Find the time for all nodes to receive the signal — the maximum shortest-path distance from k. Return -1 if any node is unreachable.

function networkDelayTime(times: number[][], n: number, k: number): number {
  const adj: [number, number][][] = Array.from({ length: n + 1 }, () => [])
  for (const [u, v, w] of times) adj[u].push([v, w])

  const dist = dijkstra(n + 1, adj, k)

  let maxDist = 0
  for (let i = 1; i <= n; i++) {
    if (dist[i] === Infinity) return -1
    maxDist = Math.max(maxDist, dist[i])
  }
  return maxDist
}

Time: O((V + E) log V). Direct Dijkstra application — answer is the max of all shortest-path distances.

Cheapest Flights Within K Stops — LC 787

Find the cheapest price from src to dst with at most k stops (at most k + 1 edges). Standard Dijkstra fails here because a path that is cheaper in cost may use too many hops.

Bellman-Ford with exactly k + 1 relaxation rounds enforces the hop constraint naturally.

function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number
): number {
  let prices = new Array(n).fill(Infinity)
  prices[src] = 0

  // Relax all edges exactly k+1 times (k stops = k+1 edges from src)
  for (let i = 0; i <= k; i++) {
    const temp = [...prices]  // snapshot of previous round
    for (const [u, v, w] of flights) {
      if (prices[u] !== Infinity && prices[u] + w < temp[v]) {
        temp[v] = prices[u] + w
      }
    }
    prices = temp
  }

  return prices[dst] === Infinity ? -1 : prices[dst]
}

Why copy prices into temp? Using prices[u] (previous round) to update temp[v] (current round) enforces that each round represents exactly one additional edge hop. Without the copy, a single round could chain multiple edges, breaking the stop count.

Time: O(k × E). Space: O(V).

Bellman-Ford

Handles negative edge weights and detects negative cycles. Slower than Dijkstra but more general.

Algorithm: Relax every edge V − 1 times. After V − 1 rounds, all shortest paths with at most V − 1 edges are found (the longest possible shortest path in a graph with V nodes). A V-th round that still improves any distance proves a negative cycle.

// Returns distances, or null if a negative cycle is reachable from src
function bellmanFord(
  n: number,
  edges: [number, number, number][],  // [u, v, weight]
  src: number
): number[] | null {
  const dist = new Array(n).fill(Infinity)
  dist[src] = 0

  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
      }
    }
  }

  // V-th relaxation detects 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). Space: O(V).

When to prefer Bellman-Ford over Dijkstra:

• Graph has negative edge weights (Dijkstra’s invariant breaks with negatives)
• Need to detect negative cycles
• Hop-count constraint exists (LC 787 pattern — run fixed rounds)
• Graph given as an edge list (Bellman-Ford operates directly on edges)

Shortest Path in Binary Matrix — LC 1091

Find the shortest clear path from (0, 0) to (n-1, n-1) in a binary matrix (0 = passable, 1 = blocked). Movement is 8-directional.

Use BFS, not Dijkstra. All edges have weight 1 (unweighted graph). BFS finds shortest paths in unweighted graphs in O(V + E) — no heap needed.

function shortestPathBinaryMatrix(grid: number[][]): number {
  const n = grid.length
  if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1
  if (n === 1) return 1

  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
  const queue: [number, number, number][] = [[0, 0, 1]]  // [row, col, dist]
  grid[0][0] = 1  // mark visited in-place

  while (queue.length > 0) {
    const [r, c, dist] = queue.shift()!
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc
      if (nr < 0 || nc < 0 || nr >= n || nc >= n || grid[nr][nc] !== 0) continue
      if (nr === n - 1 && nc === n - 1) return dist + 1
      grid[nr][nc] = 1
      queue.push([nr, nc, dist + 1])
    }
  }

  return -1
}

Time: O(n²). Space: O(n²).

Marking cells visited by setting grid[nr][nc] = 1 avoids a separate visited set. If the input grid must not be mutated, copy it first.

Floyd-Warshall

All-pairs shortest path — computes shortest distances between every pair of nodes in O(V³).

When to use: You need distances from all nodes to all other nodes, and V is small (typically V ≤ 500). For large sparse graphs, run Dijkstra from every source instead.

function floydWarshall(n: number, edges: [number, number, number][]): number[][] {
  // dist[i][j] = shortest path from i to j
  const dist: number[][] = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity))
  )

  for (const [u, v, w] of edges) {
    dist[u][v] = Math.min(dist[u][v], w)
    // For undirected: dist[v][u] = Math.min(dist[v][u], w)
  }

  // Relax through every possible intermediate node k
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j])
        }
      }
    }
  }

  return dist
}

Time: O(V³). Space: O(V²).

Negative cycle detection: after running the algorithm, check if any dist[i][i] < 0. If yes, node i is on a negative cycle.

Minimum Spanning Tree

An MST connects all V vertices with minimum total edge weight using exactly V − 1 edges and no cycles. Two approaches dominate interviews.

Kruskal’s — sort edges, add greedily with DSU

Sort edges by weight ascending. Add an edge if it connects two previously disconnected components (DSU union returns true). Stop when V − 1 edges are added.

class DSU {
  private parent: number[]
  private 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])
    return this.parent[x]
  }

  union(x: number, y: number): boolean {
    const px = this.find(x), py = this.find(y)
    if (px === py) return false
    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
  }
}

function kruskalMST(n: number, edges: [number, number, number][]): number {
  edges.sort((a, b) => a[2] - b[2])
  const dsu = new DSU(n)
  let totalWeight = 0, edgesUsed = 0

  for (const [u, v, w] of edges) {
    if (dsu.union(u, v)) {
      totalWeight += w
      if (++edgesUsed === n - 1) break
    }
  }

  return edgesUsed === n - 1 ? totalWeight : -1  // -1 if graph is disconnected
}

Time: O(E log E) dominated by sorting. Space: O(V).

Prim’s — grow MST greedily from any starting node

Start at any vertex. Repeatedly add the cheapest edge connecting the current MST to a new vertex.

function primMST(n: number, adj: [number, number][][]): number {
  const inMST = new Array(n).fill(false)
  const heap = new MinHeap()
  heap.push([0, 0])  // [weight, node], start from node 0

  let totalWeight = 0, nodesAdded = 0

  while (heap.size > 0 && nodesAdded < n) {
    const [w, u] = heap.pop()!
    if (inMST[u]) continue
    inMST[u] = true
    totalWeight += w
    nodesAdded++
    for (const [v, weight] of adj[u]) {
      if (!inMST[v]) heap.push([weight, v])
    }
  }

  return nodesAdded === n ? totalWeight : -1
}

Time: O((V + E) log V). Space: O(V + E).

When each is better: Kruskal’s is simpler when the graph is given as an edge list. Prim’s is better on dense graphs (E approaches V²) because it only ever considers neighbors of current MST nodes.

Algorithm comparison

Decision rule:

• Unweighted graph → BFS
• Non-negative weights, single source → Dijkstra
• Negative weights or hop constraint → Bellman-Ford
• All-pairs distances → Floyd-Warshall (small V) or Dijkstra from each source (sparse)
• Dependency ordering, scheduling → Topo Sort