Stop 21 · Data Structures & AlgorithmsTopics · 9/17

Graph

In short

Friend suggestions, Google Maps routes and dependency trees in npm are all graphs. In interviews, a grid of 0s and 1s is usually a graph wearing a disguise.

A structure of nodes connected by edges, modeling relationships and networks — traversed via BFS/DFS, one of the richest problem categories in interviews.

The jaadu on a metro platform points at a simple diagram of coloured dots and lines.

Think of it like this

The Delhi Metro map

Stations are nodes and the lines between them are edges. Asking 'fewest stops from Rajiv Chowk to Hauz Khas' means checking all stations one stop away, then two stops, and so on. That's BFS.

Watch it happen

BFS from A, level by level

A (start)

1/5Start at A with distance 0. The queue holds just A.

The big ideas

What you need to know

Nodes and edges

Nodes are things, edges are connections. Edges can be one-way (directed) or two-way, and can carry weights.

Store it as an adjacency list

A Map from each node to its list of neighbours. It's compact and quick to loop over.

Always track visited

Graphs can have cycles. Without a visited Set, you'll loop forever.

BFS finds shortest paths

In an unweighted graph, BFS reaches each node by the fewest edges. Weighted graphs need Dijkstra.

See it in code

Walk through the code

1// graph: Map of node -> array of neighbours2function bfs(graph, start) {3  const dist = new Map([[start, 0]]);4  const queue = [start];5 6  for (let i = 0; i < queue.length; i++) {7    const node = queue[i];8    for (const next of graph.get(node) ?? []) {9      if (dist.has(next)) continue; // already visited10      dist.set(next, dist.get(node) + 1);11      queue.push(next);12    }13  }14  return dist;15}

1/4The start node has distance 0 and is the first in the queue.

Every node is queued once and every edge checked once, so time is O(V + E). The dist Map and queue hold up to V nodes, so space is O(V).

Save yourself the pain

Common mistakes

Oops

Marking a node visited only when you take it out of the queue.

Do this instead

Mark it when you add it. Otherwise the same node can be queued many times.

Oops

Using BFS for shortest paths when edges have different weights.

Do this instead

BFS counts edges, not distance. Use Dijkstra when weights differ.

Your mission

Islands and beyond

~45 min

Quick check

Every road in a city graph is the same length. Which algorithm finds the fewest roads between two places?

Go deeper

1Implement graph representations: adjacency list and adjacency matrix.
2Solve classic problems: number of islands, course schedule (cycle detection), shortest path.
3Practice both BFS and DFS traversal, and know when each is the better fit.