Stop 21 · Data Structures & AlgorithmsTopics · 9/17

Graph

In short

Friend suggestions, flight routes, service dependencies, course prerequisites: all graphs. Learn BFS and DFS well and you can attack a huge family of interview problems.

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

The purple blob connects pinned friend photos on a corkboard with red string.

Think of it like this

Your college friend circle

Pin everyone's photo on a corkboard and tie a string between people who know each other. "Is Riya connected to Kabir?" or "How many hops apart are they?" are graph questions. People are nodes, strings are edges.

Watch it happen

BFS from A, using a queue

enqueue(A)

Front of the queue is coloured

1/8Start at A. Mark it visited and put it in the queue.

The big ideas

What you need to know

Adjacency list

Store each node's neighbours in a list, like { A: ["B", "C"] }. It's compact and the usual interview choice.

BFS: level by level

Uses a queue. In an unweighted graph, it finds the shortest path in number of hops.

DFS: go deep first

Uses recursion or a stack. Good for exploring everything, counting islands and detecting cycles.

Always track visited

Graphs can loop back. Without a visited set, your search runs in circles forever.

See it in code

Walk through the code

1const graph: Record<string, string[]> = {2  A: ["B", "C"], B: ["A", "D"], C: ["A", "D"], D: ["B", "C"],3};4 5function bfs(start: string): string[] {6  const visited = new Set([start]);7  const queue = [start];8  for (let i = 0; i < queue.length; i++) {9    for (const next of graph[queue[i]]) {10      if (!visited.has(next)) { visited.add(next); queue.push(next); }11    }12  }13  return queue; // visit order: ["A", "B", "C", "D"]14}

1/3The graph as an adjacency list: each node lists who it's connected to.

The for loop with an index acts as the queue's front pointer, so we never pay for shift(). Time is O(V + E).

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 hops. For weighted edges, like distances in km, use Dijkstra's algorithm with a heap.

Your mission

Graph traversal practice

~45 min

Quick check

You need the fewest hops between two users in a friend graph. Which search fits best?

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.