cf.completefrontend
GRAPHS · FOUNDATION

Graph representation

Turn a list of connections into an adjacency list, so you can ask "who is next to this node?" in one step.

Time O(n + e)Space O(n + e)6 practice problemsStep-through picture

The idea

A graph is a set of things, called nodes, and connections between them, called edges. Users who follow each other, web pages that link to each other, and JavaScript files that import each other are all graphs.

Problems usually hand you the edges as a plain list, like [[0, 1], [1, 2]], which means "0 is connected to 1, and 1 is connected to 2". That list is hard to work with: to find the neighbors of node 1 you would have to scan every edge. So the first step of almost every graph algorithm is to build an adjacency list: an array where graph[node] holds the list of nodes that node connects to.

Edges can be directed (one way, like "A imports B") or undirected (both ways, like "A and B are friends"). For an undirected edge you store it twice: b in a's list and a in b's list.

An everyday example

A contact list on every phone

Imagine a town where you only have a long paper list of every phone call ever made: "Ana called Ben, Ben called Cara...". To find everyone Ben talks to, you would read the whole list. Instead, every person keeps their own contact list on their phone. Now finding Ben's contacts means opening Ben's phone. An adjacency list gives every node its own contact list.

How the example maps to the code
In the exampleIn the code
The town's peopleNodes numbered 0 to n - 1
The long paper list of callsThe edges array
One person's contact listgraph[node]
Two friends saving each other's numberAn undirected edge stored in both lists

From the slow way to graph representation

  1. Start with the input exactly as it comes: a list of e pairs. To find the neighbors of one node, you read every pair and keep the ones that touch it. That costs e checks for one question. A search like BFS asks that question once for every node, so it pays about n * e checks: 20 billion for a graph with 100,000 nodes and 200,000 edges.
  2. Notice what is wasteful. The answer for node x never changes, yet every question reads the same pairs again. It is better to do the reading once, ahead of time, and sort each pair into the place where it will be asked about later, the way a post office sorts letters into one box per house.
  3. One way to sort them is a table with one row and one column per node, an adjacency matrix. It answers "is a next to b?" in one step. But it always has n * n cells, most of them empty when edges are few, and listing one node's neighbors still means reading a whole row of n cells.
  4. So keep only what exists: one list per node, holding just the nodes it connects to. Build them in a single pass over edges, pushing to into graph[from], and also from into graph[to] when the edge works both ways. That loop is building an adjacency list.

How it works

  1. Make graph, an array with one empty list for every node from 0 to n - 1.
  2. Go through each pair [from, to] in edges.
  3. Add to to graph[from], because from connects to to.
  4. If the graph is undirected, also add from to graph[to], because the connection works both ways.
  5. Return graph. Now graph[node] lists the neighbors of node.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function buildGraph(n, edges, directed = false) {
  2. const graph = Array.from({ length: n }, () => []);
  3. for (const [from, to] of edges) {
  4. graph[from].push(to);
  5. if (!directed) graph[to].push(from);
  6. }
  7. return graph;
  8. }

How fast it is

TimeO(n + e)
Extra memoryO(n + e)

It makes one list per node (n) and adds each edge once or twice (e). The lists hold exactly those entries.

  • Best caseO(n)

    edges is empty. The loop never runs, but making n empty lists still costs n steps.

  • Average caseO(n + e)

    Any normal input: n steps to make the lists and one or two pushes per edge.

  • Worst caseO(n + e)

    A dense graph where every pair is connected. Then e is about n * n / 2, so this is also O(n²), but it is still one pass over the input.

Common mistakes

  • Writing new Array(n).fill([]). Every node then shares the same list, so every node seems connected to everything. Use Array.from({ length: n }, () => []).
  • Forgetting the second push for an undirected graph. Then you can walk from a to b but not back.
  • Adding the reverse edge for a directed graph. "A imports B" does not mean "B imports A", and cycle checks give wrong answers.
  • Forgetting nodes that have no edges. They still need an empty list, or graph[node] is undefined and the loop crashes.

When to use it

Look for these clues in a problem:

  • The input is n plus a list of pairs like [from, to] or [from, to, weight].
  • The statement talks about connections: follows, links, imports, roads, cables, or dependencies.
  • You need to visit the neighbors of a node again and again.
  • The question asks about degrees: how many edges go in or out of a node.

Check yourself

Answer each one in your head first, then open it.

An undirected graph has e edges. How many entries do all the lists hold together?

Exactly 2e, because every edge is pushed into both ends' lists. In the trace, 4 edges gave 8 entries.

Why does new Array(n).fill([]) give wrong results?

fill puts the same array object in every slot. A push for one node changes that one shared array, so every node seems to have every neighbor.

In a directed graph, what does graph[x].length tell you, and what does it not?

It is the out-degree: how many edges leave x. The in-degree, edges arriving at x, needs a separate count or a reverse list.

How many cells would an adjacency matrix need for 50,000 nodes?

50,000 times 50,000, which is 2.5 billion cells, even if the graph has only a few thousand edges.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule: after it has handled some of the edges, graph[x] lists the other end of every handled edge that touches x, and nothing else. Before the loop, no edges are handled and every list is empty, so the rule is true.

Each step keeps the rule. Handling [from, to] adds to to graph[from] and, for an undirected graph, from to graph[to]. Those are exactly the two nodes this edge touches, and no other list changes. The rule depends on the lists being separate arrays: if every node shared one array, one push would show up in all of them.

The loop ends after the last edge, because for...of walks the array once. At that point every edge is handled, so by the rule graph[x] is exactly the list of x's neighbors. Any later algorithm can read it in time proportional to that node's degree instead of to e.

Going deeper

3 more ideas

Adjacency list or adjacency matrix

An adjacency matrix is an n by n grid where matrix[a][b] is 1 (or the weight) when there is an edge from a to b. It answers "is there an edge from a to b?" in one step, but it always uses n * n cells, even when there are few edges. A graph of 100,000 users would need 10 billion cells. An adjacency list only stores the edges that exist, so it is the usual choice. Use a matrix when n is small (a few hundred) or when the graph is dense.

Storing weights

When an edge has a weight, such as a travel time or a cost, store pairs instead of plain nodes: graph[from].push([to, weight]). Then a loop reads both at once with for (const [next, weight] of graph[node]).

Nodes that are not numbers

If nodes are names like "app.js", use a Map from name to list instead of an array: graph.get(name). Remember to create an empty list for a name the first time you see it, including names that only ever appear as a to.

Work it by hand

Every step in a table, with why

Build the adjacency lists of an undirected graph with 6 nodes and 4 edges. Node 5 has no edges at all.

n = 6, edges = [[3, 1], [0, 4], [1, 4], [4, 2]], directed = false

Stepfromtograph after this stepWhat happensWhy
1--[[], [], [], [], [], []]Make 6 empty listsArray.from calls the arrow function 6 times, so every node gets its own separate empty list.
231[[], [3], [], [1], [], []]Push 1 to list 3, 3 to list 1The edge works both ways, so it is stored twice: once in each end's list.
304[[4], [3], [], [1], [0], []]Push 4 to list 0, 0 to list 4Lists fill in the order the edges arrive. Nothing is sorted.
414[[4], [3, 4], [], [1], [0, 1], []]Push 4 to list 1, 1 to list 4Node 1 now has two neighbors. Its list grows at the end.
542[[4], [3, 4], [4], [1], [0, 1, 2], []]Push 2 to list 4, 4 to list 2Node 4 collects a third neighbor. It is the busiest node, with degree 3.
6--sameReturn graphThe loop has read every edge once. Node 5 still has its empty list, so graph[5] is [] and not undefined.

The lists hold 8 entries for 4 edges, two per edge. With directed = true the same edges give [[4], [4], [], [1], [2], []]: 4 entries, and only the from side knows about each edge.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Graph representationO(n + e)O(n + e)The default for almost every graph problem: build once, then each neighbor lookup costs only that node's degree.
Adjacency matrixO(n²)O(n²)The graph is small or dense, and you often ask whether one specific edge exists.
Scanning the raw edge listO(n · e)O(e)You only read the edges once in a fixed order, as Kruskal's algorithm or union-find do. For repeated neighbor lookups it is far too slow.

Extra memory: O(n + e): n arrays, plus one entry per directed edge or two per undirected edge. A matrix would need n * n cells instead.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Graph representation and the other approaches, on a scale where each line up is 10 times more steps.
  • Graph representation O(n + e)
  • Adjacency matrix, Scanning the raw edge list O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Graph representation202,0002 million
Adjacency matrix1001 million1 trillion
Scanning the raw edge list1001 million1 trillion

Inputs that need care

5 tricky inputs
No edges: n = 3, edges = []
The loop never runs and the result is [[], [], []]. Every node exists and has no neighbors.
A self-loop: [[2, 2]], undirected
Both pushes go to the same list, so graph[2] becomes [2, 2]. That matches the usual rule that a self-loop adds 2 to a node's degree. If your problem forbids self-loops, skip pairs where from === to.
The same edge twice: [[0, 1], [0, 1]]
Both copies are stored, so graph[0] is [1, 1]. Searches still work because they skip visited nodes, but degree counts are too high. Use a Set per node if duplicates must collapse.
Nodes numbered from 1: n = 4, edges = [[1, 2], [4, 1]]
There is no list at index 4, so graph[4].push throws "Cannot read properties of undefined (reading 'push')". Either make n + 1 lists or subtract 1 from every node first.
Node names instead of numbers: [["app.js", "util.js"]]
An array can't be indexed by a name. Use a Map from name to list, and create an empty list the first time a name appears, on either side of an edge.

Variations and follow-ups

Twists interviewers add

Weighted adjacency list

Push pairs instead of plain nodes: graph[from].push([to, weight]). Dijkstra's algorithm and 0-1 BFS read both values at once with for (const [next, weight] of graph[node]).

Adjacency matrix

Make an n by n grid of zeros and set matrix[from][to] = 1 (and the reverse for undirected edges). Checking one edge is a single lookup, but memory is n * n whatever the edge count. It suits small dense graphs, such as 200 nodes where most pairs are connected.

A Map of Sets

Use Map<string, Set<string>> when nodes have names, when duplicate edges must be ignored, or when you need a fast "is there an edge from a to b?" check. Each node's set answers that with has in about one step.

Reverse lists and in-degrees

Some algorithms also need the edges that come into a node. Build a second structure, reverse[to].push(from), in the same loop, or just count indegree[to]++ as Kahn's algorithm does.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from the input shape: n plus a list of pairs, or words like prerequisites, connections, roads, or imports. Building the adjacency list is almost always the first three lines of your answer.
  • Before coding, say out loud whether edges are directed and whether nodes start at 0 or 1. Those two facts decide whether you push once or twice and how many lists you make.
  • Test by hand on a node with no edges and on one directed edge. The first catches a missing empty list, the second catches an extra reverse push.
  • A common follow-up is "why not a matrix?". Answer with numbers: 100,000 nodes would need 10 billion cells, while the lists only store the edges that exist.

Where frontend code uses it

The same idea in real UI code
  • Bundlers such as webpack, Rollup, and Vite build a module graph: each file maps to the list of files it imports.
  • The DOM is a graph too: each element keeps children and a parentNode, which is an adjacency list stored on the nodes themselves.
  • Diagram and flowchart editors store boxes as nodes and arrows as edges, often as a list of edges in the saved JSON that is turned into adjacency lists when loaded.

Related algorithms