What a graph is
You're building a social network. People are linked by friendships, and you keep being asked: are Ana and Ben connected? What's the shortest chain between them? How many separate friend groups exist? The same shape powers maps (cities + roads), the web (pages + links), and dependencies (tasks that must precede others). Arrays and trees can't capture arbitrary "this links to that."
A graph is just nodes (also called vertices — the people) joined by edges (the friendships). A node's neighbours are those directly connected to it, and edges can be undirected (a friendship, both ways) or directed (a follow, one way). The standard storage is an adjacency list — for each node, the list of its direct neighbours — so "who are Ana's friends?" is one instant lookup instead of scanning every edge.
0
1
2
3
4
Quick check
An adjacency list stores, for each node…
Answer it in the interactive lesson to keep your progress.
The core operations: two ways to explore
Beyond looking up neighbours, the fundamental move is to explore outward from a node — and there are two ways, each with its own tool:
- BFS (breadth-first) uses a queue and floods outward level by level, so it reaches the nearest nodes first — ideal for shortest chains.
- DFS (depth-first) uses recursion or a stack and commits to one path all the way to its end before backing up — ideal for "is there any path" and cycle questions.
Both carry a visited set so they never re-process a node. Here's the adjacency list you'd walk:
const graphAdj = [
[1, 2], // vertex 0 -> 1, 2
[0, 3], // vertex 1 -> 0, 3
[0, 3], // vertex 2 -> 0, 3
[1, 2, 4], // vertex 3 -> 1, 2, 4
[3], // vertex 4 -> 3
];
console.log('vertex 0 neighbours:', graphAdj[0]); // [1, 2]
console.log('vertex 3 neighbours:', graphAdj[3]); // [1, 2, 4]
console.log('does 0 connect to 1?', graphAdj[0].includes(1)); // trueQuick check
You need the SHORTEST chain of friendships between two people. Predict the right tool.
Answer it in the interactive lesson to keep your progress.
Your first graph problem: BFS from a node
Starting from one person (Ana), visit everyone reachable, nearest first. BFS (breadth-first search) does this with a queue and a visited set, fanning out level by level — which is exactly why it finds the shortest chain of connections.
The steps
- Put the start node in a queue and mark it visited.
- While the queue isn't empty, dequeue a node and process it.
- For each of its unvisited neighbours: mark it visited and enqueue it.
- Because a queue is first-in-first-out, everyone one hop away is visited before anyone two hops away.
Trace it from Ana:
- visit Ana → enqueue her friends Ben, Cara
- visit Ben → enqueue his unvisited friends
- visit Cara → …
That level-by-level order is why BFS finds the shortest chain. In the animation, watch the frontier spread like a ripple: every node at distance 1 turns visited before any node at distance 2. Also watch the queue readout — nodes leave it in exactly the order they entered. In JavaScript, one way to write those steps:
This section has a step-by-step animation in the interactive lesson.
const bfsAdj = [[1, 2], [0, 3], [0, 3], [1, 2]];
function bfsOrder(adj, start) {
const seen = [start]; // mark the start visited
const queue = [start]; // nodes waiting to be processed
while (queue.length) {
const u = queue.shift(); // dequeue the front (nearest) node
for (const v of adj[u]) {
if (!seen.includes(v)) { // an unvisited neighbour
seen.push(v); // mark it visited...
queue.push(v); // ...and enqueue it for a later round
}
}
}
return seen;
}
console.log('BFS from 0:', bfsOrder(bfsAdj, 0)); // [0, 1, 2, 3]Quick check
BFS finds shortest paths (fewest edges) because it…
Answer it in the interactive lesson to keep your progress.
Take it further — count the components (islands)
One traversal reaches one connected group. So to count how many separate groups a graph has, just start a fresh traversal from every not-yet-seen node — each new start is one more component. This is the shape behind "number of islands." Here's a graph with three pieces (
0-1, 2-3, and a lone 4) — three traversal starts, three components.In the animation, watch the counter: it ticks up only when a traversal starts at an unseen node, never during the flood itself. The lone node
4 still costs one full start — a component of size 1 is still a component.This section has a step-by-step animation in the interactive lesson.
function countComponents(n, adj) {
const seen = new Set();
let count = 0;
function dfs(u) {
seen.add(u);
for (const v of adj[u]) if (!seen.has(v)) dfs(v);
}
for (let i = 0; i < n; i++) {
if (!seen.has(i)) { count++; dfs(i); } // a new start = one more group
}
return count;
}
const pieces = [[1], [0], [3], [2], []]; // 0-1, 2-3, lone 4
console.log(countComponents(5, pieces)); // 3Quick check
Nodes 0..5, edges 0-1, 1-2, 4-5. Predict the number of components.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- No visited set. Graphs have cycles (Ana-Ben-Ana). Without marking visited nodes, BFS/DFS loop forever. This is the number-one graph bug — mark on enqueue/visit.
- Directed vs. undirected. A friendship goes both ways; a Twitter follow does not. Add edges in one direction or both to match the problem.
- Marking too late. In BFS, mark a node when you enqueue it, not when you dequeue it, or it can enter the queue multiple times.
Quick check
Traversing a graph with a cycle and NO visited set will…
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, both BFS and DFS touch every vertex once and every edge once (V vertices, E edges):
| Item | Cost | Why |
|---|---|---|
| BFS / DFS traversal | O(V + E) time | each node and edge processed once |
| visited set + queue/stack | O(V) space | at most every node held once |
| adjacency list storage | O(V + E) space | far leaner than a V × V matrix when sparse |
Key takeaways:
- A graph is nodes + edges; store neighbours in an adjacency list.
- BFS (queue) finds nearest-first / shortest unweighted paths; DFS (stack/recursion) plunges deep for path & cycle questions.
- The visited set is not optional — cycles make an unguarded traversal loop forever. Traversal is
O(V + E).
This lets you model anything as nodes and edges. These classics each get their own lesson later (no need to know them yet): number of islands / connected components (flood fill), shortest path in an unweighted graph (BFS; add a heap for weighted — Dijkstra), and course schedule / topological sort (DFS with cycle detection). Next up in order: Union-Find — a near-instant way to track which pieces belong to the same group.