JS-201 · Lesson 10 of 12 · 28 min
Graphs and traversal
▶ Video coming soon A video version of this lesson is on the way.
The December 2027 hamper drive is the biggest delivery job of the Food Hub's year. In 2026 it sent out about 287 hampers, and the plan for 2027 is to deliver some of them to six pick-up points across Madison: a library, a school, a church, a health clinic, an arena and a farmers' market building. Dev Bhatt, the communications lead, has asked for a page that tells drivers the quickest route between any two points. At the tenth session, on Thursday, October 7, Gareth draws the points on the whiteboard, joins them with lines for the roads between them and writes the van's driving time on each line. "That drawing is a graph," he says. "Most of the hard problems you will meet are graph problems in disguise."
What a graph is
A graph is a set of vertices, also called nodes, connected by edges. A tree is a special graph, but a general graph can have cycles, several paths between the same two vertices, and vertices that are not connected at all. In an undirected graph, an edge works both ways, like a two-way road. In a directed graph, each edge goes one way, like a one-way street or a task that must come before another. In a weighted graph, each edge has a number, such as minutes of driving.
Two vertices joined by an edge are neighbors, and the number of edges at a vertex is its degree. A path is a sequence of vertices each joined to the next by an edge, and a cycle is a path that returns to where it started. An undirected graph is connected if there is a path between every pair of vertices. The pick-up point graph below is undirected, weighted and connected.
Storing a graph
The usual way to store a graph in code is an adjacency list: for each vertex, a list of its neighbors, with the edge weight if there is one. In JavaScript, a Map from vertex name to an array of edges works well. It uses memory in proportion to the number of vertices plus edges, written O(V + E), and listing a vertex's neighbors costs only as much as the number of neighbors.
The alternative is an adjacency matrix, a V × V table in which row a, column b holds the weight of the edge from a to b, or nothing. Checking whether two vertices are joined is O(1), but the table needs O(V²) memory even if most pairs have no edge. Road networks, social networks and almost all real graphs are sparse, with far fewer edges than possible pairs, so adjacency lists are the normal choice.
const roads = [ // [place, place, minutes by van]
['Hub', 'Library', 6], ['Hub', 'School', 9], ['Library', 'School', 4], ['Library', 'Church', 8],
['School', 'Clinic', 5], ['Church', 'Clinic', 3], ['Church', 'Rink', 7], ['Clinic', 'Market', 10],
['Rink', 'Market', 4], ['School', 'Market', 16],
];
function buildGraph(edges) {
const g = new Map();
for (const [a, b, w] of edges) {
if (!g.has(a)) g.set(a, []);
if (!g.has(b)) g.set(b, []);
g.get(a).push({ to: b, w });
g.get(b).push({ to: a, w }); // roads go both ways
}
return g;
}
const graph = buildGraph(roads);
for (const [place, edges] of graph) {
console.log(place.padEnd(8), 'degree', edges.length, '->', edges.map((e) => e.to + ' ' + e.w).join(', '));
}
console.log('vertices', graph.size, '| edges', roads.length);Hub degree 2 -> Library 6, School 9 Library degree 3 -> Hub 6, School 4, Church 8 School degree 4 -> Hub 9, Library 4, Clinic 5, Market 16 Church degree 3 -> Library 8, Clinic 3, Rink 7 Clinic degree 3 -> School 5, Church 3, Market 10 Rink degree 2 -> Church 7, Market 4 Market degree 3 -> Clinic 10, Rink 4, School 16 vertices 7 | edges 10
What this code does
buildGraph turns the list of roads into a Map from each place to its edges. Each road is added twice, once in each direction, because the graph is undirected. Printing the Map shows every place's neighbors and driving times, and each place's degree is just the length of its edge list.
Breadth-first search
Breadth-first search, or BFS, explores a graph outwards from a starting vertex in layers: first the start, then all its neighbors, then all their neighbors not yet seen, and so on. It uses a queue, from Lesson 4, of vertices waiting to be explored, and a Set or Map of vertices already seen, so that no vertex is visited twice even when the graph has cycles. Every vertex and every edge is handled at most once or twice, so BFS is O(V + E).
The order matters: because BFS finishes each layer before starting the next, the first time it reaches a vertex is along a path with the fewest edges. Recording, for each vertex, the vertex it was reached from gives a parent map, and following parents back from the destination rebuilds that path. For a driver, fewest edges means fewest stops, whatever the driving times.
const roads = [ // [place, place, minutes by van]
['Hub', 'Library', 6], ['Hub', 'School', 9], ['Library', 'School', 4], ['Library', 'Church', 8],
['School', 'Clinic', 5], ['Church', 'Clinic', 3], ['Church', 'Rink', 7], ['Clinic', 'Market', 10],
['Rink', 'Market', 4], ['School', 'Market', 16],
];
function buildGraph(edges) {
const g = new Map();
for (const [a, b, w] of edges) {
if (!g.has(a)) g.set(a, []);
if (!g.has(b)) g.set(b, []);
g.get(a).push({ to: b, w });
g.get(b).push({ to: a, w }); // roads go both ways
}
return g;
}
const graph = buildGraph(roads);
function bfs(graph, start) {
const hops = new Map([[start, 0]]);
const parent = new Map([[start, null]]);
const queue = [start];
for (let i = 0; i < queue.length; i++) { // array as a queue with a moving head
const v = queue[i];
for (const { to } of graph.get(v)) {
if (!hops.has(to)) {
hops.set(to, hops.get(v) + 1);
parent.set(to, v);
queue.push(to);
}
}
}
return { order: queue, hops, parent };
}
function pathTo(parent, end) {
const path = [];
for (let v = end; v !== null; v = parent.get(v)) path.push(v);
return path.reverse();
}
const r = bfs(graph, 'Hub');
console.log('visit order:', r.order.join(' '));
console.log('stops from Hub:', [...r.hops].map(([p, h]) => p + ' ' + h).join(', '));
console.log('fewest stops to Market:', pathTo(r.parent, 'Market').join(' -> '));visit order: Hub Library School Church Clinic Market Rink stops from Hub: Hub 0, Library 1, School 1, Church 2, Clinic 2, Market 2, Rink 3 fewest stops to Market: Hub -> School -> Market
What this code does
bfs starts at the Hub and keeps an array of places to explore, reading it from the front so it behaves as a queue. Each newly seen neighbor is given a hop count one more than the place it was reached from and is remembered with that place as its parent. Following parents back from the Market gives the route with the fewest stops: two hops, through the School.
Depth-first search
Depth-first search, or DFS, explores as far as possible along one path before backing up to try another. It can be written with recursion, letting the call stack remember where to back up to, or with an explicit stack, as in Lesson 6. Like BFS it marks vertices as seen and runs in O(V + E), but it visits them in a different order and does not find fewest-edge paths.
DFS is the tool for questions about structure rather than distance: can this vertex be reached at all, which vertices form separate groups, does the graph contain a cycle, and in what order can dependent tasks be done. Suppose road closures for the Santa Claus parade cut four roads: Library to Church, Church to Clinic, Clinic to Market and School to Market. DFS shows which pick-up points can still be reached from the Hub, and which form a separate group.
const roads = [ // [place, place, minutes by van]
['Hub', 'Library', 6], ['Hub', 'School', 9], ['Library', 'School', 4], ['Library', 'Church', 8],
['School', 'Clinic', 5], ['Church', 'Clinic', 3], ['Church', 'Rink', 7], ['Clinic', 'Market', 10],
['Rink', 'Market', 4], ['School', 'Market', 16],
];
function buildGraph(edges) {
const g = new Map();
for (const [a, b, w] of edges) {
if (!g.has(a)) g.set(a, []);
if (!g.has(b)) g.set(b, []);
g.get(a).push({ to: b, w });
g.get(b).push({ to: a, w }); // roads go both ways
}
return g;
}
const graph = buildGraph(roads);
function dfs(graph, start, seen = new Set(), order = []) {
seen.add(start);
order.push(start);
for (const { to } of graph.get(start)) if (!seen.has(to)) dfs(graph, to, seen, order);
return order;
}
console.log('depth-first from Hub:', dfs(graph, 'Hub').join(' '));
const closed = new Set(['Library|Church', 'Church|Clinic', 'Clinic|Market', 'School|Market']);
const open = roads.filter(([a, b]) => !closed.has(a + '|' + b));
const parade = buildGraph(open);
const seen = new Set(), groups = [];
for (const place of parade.keys()) if (!seen.has(place)) groups.push(dfs(parade, place, seen));
console.log('groups during the parade:', groups.map((g) => g.join(' ')).join(' | '));depth-first from Hub: Hub Library School Clinic Church Rink Market groups during the parade: Hub Library School Clinic | Church Rink Market
What this code does
dfs marks a place as seen and then calls itself on each neighbor not yet seen, so it goes as deep as it can before returning. To find separate groups, the second part runs dfs from every place not already reached, and each run collects one connected group. With the four roads closed, the Church, Rink and Market form a group of their own that cannot be reached from the Hub.
The loop that starts a new DFS from every unvisited vertex counts the connected components of the graph. The same pattern finds groups of volunteers who can share rides, clusters of related shifts, or islands of a map that are not joined to the rest.
Directed graphs and task order
The hamper drive has a schedule of tasks, and some tasks depend on others: hampers cannot be packed until the donations are sorted and the boxes are ordered, labels need the final list of families, and the vans cannot be loaded until the hampers are packed and labeled. This is a directed graph, with an edge from each task to every task that depends on it. Because nothing can depend on itself, even indirectly, it must have no cycles: it is a directed acyclic graph, or DAG.
A topological order lists the tasks so that every task comes after all the tasks it depends on. Kahn's algorithm finds one by counting, for each task, how many tasks it still waits for. Tasks waiting for nothing are ready; take one, add it to the order, and reduce the count of each task that depended on it, which may make more tasks ready. If tasks are left over when no task is ready, the dependencies contain a cycle and no order exists, which is a useful check on a schedule.
const tasks = {
'Order boxes': [], 'Collect donations': [], 'Confirm families': [],
'Sort donations': ['Collect donations'], 'Pack hampers': ['Order boxes', 'Sort donations'],
'Print labels': ['Confirm families'], 'Label hampers': ['Pack hampers', 'Print labels'],
'Book vans': [], 'Load vans': ['Label hampers', 'Book vans'],
};
function topoOrder(tasks) {
const waiting = new Map(), next = new Map();
for (const t in tasks) { waiting.set(t, tasks[t].length); next.set(t, []); }
for (const t in tasks) for (const before of tasks[t]) next.get(before).push(t);
const ready = [...waiting].filter(([, n]) => n === 0).map(([t]) => t);
const order = [];
for (let i = 0; i < ready.length; i++) {
const t = ready[i];
order.push(t);
for (const u of next.get(t)) { waiting.set(u, waiting.get(u) - 1); if (waiting.get(u) === 0) ready.push(u); }
}
return order.length === waiting.size ? order : null; // null means a cycle
}
topoOrder(tasks).forEach((t, i) => console.log(i + 1 + '.', t));
console.log(topoOrder({ A: ['B'], B: ['A'] }));1. Order boxes 2. Collect donations 3. Confirm families 4. Book vans 5. Sort donations 6. Print labels 7. Pack hampers 8. Label hampers 9. Load vans null
What this code does
topoOrder counts how many tasks each task waits for and starts with the tasks that wait for none. Each time a task is placed in the order, every task that depended on it waits for one task fewer, and any whose count reaches zero becomes ready. The second call, in which A and B wait for each other, returns null because no task can ever start.
Quickest routes: Dijkstra's algorithm
BFS finds the fewest stops, but drivers care about minutes. On a weighted graph, the quickest route from a start is found by Dijkstra's algorithm, published by Edsger Dijkstra in 1959. It keeps the best known time to every vertex, starting with 0 for the start and infinity for the rest. It repeatedly takes the unfinished vertex with the smallest known time, which is now final, and checks each of its edges: if going through this vertex gives a neighbor a shorter time, the neighbor's time and parent are updated, a step called relaxing the edge.
Taking the smallest unfinished vertex each time is a job for the priority queue from Lesson 4. With a binary heap, Dijkstra's algorithm runs in O((V + E) log V). It requires that no edge has a negative weight, which is true of driving times; graphs with negative weights need other algorithms such as Bellman-Ford.
const roads = [ // [place, place, minutes by van]
['Hub', 'Library', 6], ['Hub', 'School', 9], ['Library', 'School', 4], ['Library', 'Church', 8],
['School', 'Clinic', 5], ['Church', 'Clinic', 3], ['Church', 'Rink', 7], ['Clinic', 'Market', 10],
['Rink', 'Market', 4], ['School', 'Market', 16],
];
function buildGraph(edges) {
const g = new Map();
for (const [a, b, w] of edges) {
if (!g.has(a)) g.set(a, []);
if (!g.has(b)) g.set(b, []);
g.get(a).push({ to: b, w });
g.get(b).push({ to: a, w }); // roads go both ways
}
return g;
}
const graph = buildGraph(roads);
class MinHeap {
constructor(less) { this.a = []; this.less = less; }
get size() { return this.a.length; }
push(x) { const a = this.a; a.push(x); let i = a.length - 1;
while (i > 0) { const p = (i - 1) >> 1; if (!this.less(a[i], a[p])) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } }
pop() { const a = this.a, top = a[0], last = a.pop();
if (a.length) { a[0] = last; let i = 0;
for (;;) { const l = 2 * i + 1, r = l + 1; let m = i;
if (l < a.length && this.less(a[l], a[m])) m = l;
if (r < a.length && this.less(a[r], a[m])) m = r;
if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } }
return top; }
}
function dijkstra(graph, start) {
const time = new Map([[start, 0]]), parent = new Map([[start, null]]), done = new Set();
const heap = new MinHeap((a, b) => a[0] < b[0]);
heap.push([0, start]);
while (heap.size > 0) {
const [t, v] = heap.pop();
if (done.has(v)) continue; // an out-of-date entry
done.add(v);
for (const { to, w } of graph.get(v)) {
const nt = t + w;
if (!time.has(to) || nt < time.get(to)) { // relax the edge
time.set(to, nt); parent.set(to, v); heap.push([nt, to]);
}
}
}
return { time, parent };
}
function pathTo(parent, end) { const p = []; for (let v = end; v !== null; v = parent.get(v)) p.push(v); return p.reverse(); }
const { time, parent } = dijkstra(graph, 'Hub');
for (const place of ['Library', 'School', 'Clinic', 'Church', 'Rink', 'Market']) {
console.log(place.padEnd(8), String(time.get(place)).padStart(2), 'min:', pathTo(parent, place).join(' -> '));
}Library 6 min: Hub -> Library School 9 min: Hub -> School Clinic 14 min: Hub -> School -> Clinic Church 14 min: Hub -> Library -> Church Rink 21 min: Hub -> Library -> Church -> Rink Market 24 min: Hub -> School -> Clinic -> Market
What this code does
dijkstra keeps the best time found so far for each place and uses the heap to take the closest unfinished place next. When a place comes off the heap for the first time its time is final, and each of its roads is checked to see whether it gives a neighbor a quicker time. The quickest route to the Market takes 24 minutes through the School and the Clinic, even though the route with fewest stops, straight from the School, takes 25.
Instead of updating entries inside the heap, this version pushes a new entry whenever a time improves and skips old entries when they come off the heap. That keeps the heap simple and is how most practical implementations work. Map apps use refinements of the same idea, such as A* search, which uses an estimate of the remaining distance to explore toward the destination first.
| Question | Algorithm | Cost |
|---|---|---|
| Which vertices can be reached? | BFS or DFS | O(V + E) |
| Fewest edges between two vertices | BFS | O(V + E) |
| Separate groups (connected components) | DFS or BFS from each unvisited vertex | O(V + E) |
| An order that respects dependencies | Topological sort (Kahn's algorithm) | O(V + E) |
| Does a directed graph have a cycle? | Kahn's algorithm or DFS | O(V + E) |
| Quickest route with non-negative weights | Dijkstra's algorithm with a heap | O((V + E) log V) |
| Shortest route visiting every vertex | No known fast algorithm | Exponential for exact answers |
The last row is a warning. Dev's page only needs routes between two points, which Dijkstra answers quickly. Planning one van's route that visits every pick-up point in the shortest total time is the traveling salesman problem, for which no algorithm is known that is fast on every input. For six points, trying every order is only 720 possibilities; for 20 it is more than two billion billion. Real delivery planners use heuristics that give good, though not always perfect, routes. Lesson 12 returns to this when Mira plans the drivers' rounds.
Try it yourself
Neighbors and degree
Complete degrees(edges) so that it returns a Map from each place to its number of roads, for an undirected list of roads given as [place, place] pairs.
Each road adds one to the degree of both places.
function degrees(edges) {
const d = new Map();
for (const [a, b] of edges) {
d.set(a, (d.get(a) ?? 0) + 1);
}
return d;
}
const roads = [['Hub', 'Library'], ['Hub', 'School'], ['Library', 'School'], ['School', 'Clinic'], ['Clinic', 'Church']];
for (const [p, n] of degrees(roads)) console.log(p, n);Try it yourself
How many stops away?
Complete stopsBetween(graph, from, to) so that it returns the fewest number of roads on a route from from to to, using breadth-first search, or -1 if to cannot be reached.
graph is a Map from each place to an array of neighboring place names.
function stopsBetween(graph, from, to) {
return graph.get(from).includes(to) ? 1 : -1;
}
const graph = new Map([
['Hub', ['Library', 'School']], ['Library', ['Hub', 'Church']], ['School', ['Hub', 'Clinic']],
['Church', ['Library', 'Rink']], ['Clinic', ['School']], ['Rink', ['Church']], ['Depot', []],
]);
console.log(stopsBetween(graph, 'Hub', 'School'), stopsBetween(graph, 'Hub', 'Rink'), stopsBetween(graph, 'Hub', 'Hub'), stopsBetween(graph, 'Hub', 'Depot'));Try it yourself
Count the groups
Complete countGroups(graph) so that it returns how many separate connected groups the undirected graph has. Run a search from every place not yet seen and count how many searches you start.
graph is a Map from each place to an array of neighboring place names.
function countGroups(graph) {
return 1;
}
const graph = new Map([
['Hub', ['Library']], ['Library', ['Hub', 'School']], ['School', ['Library']],
['Church', ['Rink']], ['Rink', ['Church']], ['Depot', []],
]);
console.log(countGroups(graph));
console.log(countGroups(new Map([['A', ['B']], ['B', ['A']]])));Common mistakes
MistakeRunning BFS or DFS without a seen set.
InsteadCycles make the search loop for ever or visit vertices many times. Mark vertices when they are first reached.
MistakeUsing BFS to find the quickest route on a weighted graph.
InsteadBFS finds the fewest edges. Use Dijkstra's algorithm when edges have different weights.
MistakeUsing Dijkstra's algorithm with negative weights.
InsteadIt assumes no edge is negative; use Bellman-Ford for negative weights.
MistakeStoring a large sparse graph as an adjacency matrix.
InsteadThe matrix needs O(V²) memory. Use an adjacency list.
MistakeForgetting to add both directions for an undirected edge.
InsteadAdd the edge to both endpoints' lists, or searches will miss routes.
Summary and key terms
- A graph has vertices joined by edges, which may be undirected or directed and may have weights.
- Neighbors, degree, paths, cycles and connectivity describe its structure.
- An adjacency list, such as a Map from vertex to an array of edges, uses O(V + E) memory and suits sparse real-world graphs, while an adjacency matrix uses O(V²).
- Breadth-first search explores in layers with a queue and a seen set, finds fewest-edge paths and, with a parent map, rebuilds them, in O(V + E).
- Depth-first search goes deep first with recursion or a stack and answers reachability, connected components and cycle questions in O(V + E).
- A directed acyclic graph of tasks can be put in topological order with Kahn's algorithm, which also detects cycles.
- Dijkstra's algorithm finds quickest routes on graphs with non-negative weights by finalizing the closest vertex each time, using a priority queue for O((V + E) log V).
- The traveling salesman problem has no known fast exact algorithm.
- graph
- A set of vertices connected by edges.
- vertex
- One point of a graph, also called a node.
- edge
- A connection between two vertices, which may have a direction and a weight.
- adjacency list
- A graph representation that lists, for each vertex, its neighbors.
- breadth-first search
- Exploring a graph in layers outward from a start, using a queue; it finds fewest-edge paths.
- depth-first search
- Exploring a graph by following one path as far as possible before backing up.
- connected component
- A group of vertices that are all reachable from one another, with no path to the rest.
- directed acyclic graph
- A directed graph with no cycles, such as a set of tasks and their dependencies.
- topological order
- An order of a DAG's vertices in which each comes after everything it depends on.
- Dijkstra's algorithm
- An algorithm for quickest paths from one vertex on a graph with non-negative weights.
Practice problems
Work each problem on paper first, then reveal the answer to check.
Why does an undirected road need adding to both places' lists?
Show answer
It can be driven in both directions, so each place is the other's neighbor.
Which search finds the route with the fewest stops?
Show answer
Breadth-first search.
What does Kahn's algorithm return if the tasks contain a cycle?
Show answer
It cannot place every task, so it reports that no order exists, null in the example.
Why can Dijkstra's algorithm treat a vertex's time as final when it comes off the heap?
Show answer
All other unfinished vertices have larger times, and with no negative edges no later route can be quicker.
How many orders of 8 pick-up points would a brute-force route planner try?
Show answer
8! = 40,320.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.