Graphs

Time Complexity

Key Points

• Build the graph first: adjacency list is the most common interview-ready format
• BFS is your first tool for shortest path in unweighted graphs
• DFS is useful for connectivity, components, and state exploration
• Visited tracking is non-negotiable: it prevents infinite loops
• For dependency problems, topological ordering often replaces recursion guessing
• For weighted shortest path, track current distance and relax edges
• Practice by writing reusable helpers: buildGraph, bfs, dfs, visit

Code Examples

function buildGraph(n, edges) {
  const graph = Array.from({ length: n }, () => [])

  for (const [from, to] of edges) {
    graph[from].push(to)
  }

  return graph
}

buildGraph(4, [[0, 1], [1, 2], [2, 3]])
// [[1], [2], [3], []]

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

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

    for (const next of graph[node]) {
      if (!seen.has(next)) {
        seen.add(next)
        queue.push(next)
      }
    }
  }

  return order
}

bfs([[1, 2], [2], [3], []], 0)  // [0, 1, 2, 3]

function dfs(graph, start) {
  const seen = new Set()
  const order = []

  function visit(node) {
    if (seen.has(node)) return
    seen.add(node)
    order.push(node)

    for (const next of graph[node]) {
      visit(next)
    }
  }

  visit(start)
  return order
}

dfs([[1, 2], [2], [3], []], 0)  // [0, 1, 2, 3]

Common Mistakes

• Forgetting to build the graph before solving the problem
• Marking visited too late (causing duplicate work or cycles)
• Assuming edges are directed when they are undirected
• Using DFS recursion for very deep graphs without considering stack limits
• Ignoring disconnected components in traversal problems

Interview Tips

• State graph representation first in your first 30 seconds
• Start with BFS or DFS on brute structure before optimizing
• If cycle exists, mention how you avoid infinite loops
• For prerequisites/dependencies, describe indegree + queue immediately

Practice Problems

Related Concepts