Overview

Medium

Directed, weighted, and how we store them

In simple words

A graph is dots (things) joined by lines (connections); many problems just ask how things are connected.

The idea

A graph is nodes joined by edges — directed or not, weighted or not. Most problems reduce to a traversal (BFS/DFS) over an adjacency list, the standard storage format.

←→stepspaceplay

1/5

Optimal

timeO(V+E)spaceO(V+E)

Neighbors per node.

1const adj = Array.from({length: V}, () => []);2for (const [u, v] of edges) {3  adj[u].push(v);4  adj[v].push(u); // omit for directed5}

Input

nodes: 5, 5 edges

Memory

visiting: —

Output

reached: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: edges (1,2), (2,3), adjacency list of 3 nodes
Output:: 1: [2], 2: [1,3], 3: [2]
Explanation:: An undirected edge is stored twice. A list costs O(V+E) space; a matrix costs O(V²) but answers 'is there an edge?' instantly.

Example 2

Input:: is (1,3) an edge?
Output:: no — but 3 is reachable
Explanation:: Adjacency is one hop; reachability is a traversal. Confusing the two is the commonest first mistake.

Finished the walkthrough? Add it to your streak.