Nodes and edges, and four questions
A tree is a graph: connected, undirected, no cycles, exactly n−1 edges. Everything in the tree lessons is a special case of everything in these three.
| Question | The two answers |
|---|---|
| Directed? | A follows B without B following A — or the edge goes both ways |
| Weighted? | Every edge has a cost (distance, time, price) — or they are all equal |
| Cyclic? | Can you get back where you started? A graph with no cycles and directions is a DAG |
| Dense or sparse? | Close to n² edges, or closer to n |
Adjacency list against adjacency matrix
Use an adjacency list. Real graphs — road networks, social graphs, dependency trees, web links — are overwhelmingly sparse: a node has a handful of neighbours, not thousands. A matrix for a million nodes needs a trillion cells to store a few million edges.
/* adjacency list — a Map from node to its neighbours */
const graph = new Map([
["a", ["b", "c"]],
["b", ["d"]],
["c", ["d"]],
["d", []],
]);
/* adjacency matrix — row i, column j is 1 when i → j */
const matrix = [
[0, 1, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
];| List | Matrix | |
|---|---|---|
| Memory | O(n + e) | O(n²), even for three edges |
| Is there an edge a→b? | O(degree) | O(1) |
| Every neighbour of a | O(degree) | O(n) — you scan the whole row |
| Add an edge | O(1) | O(1) |
| Good for | Sparse graphs — almost everything real | Dense graphs, and matrix mathematics |
Weights, and the shapes they take
Forgetting one direction of an undirected edge is the most common graph bug, and it produces a program that works on some inputs and quietly loses others. Build undirected graphs through a helper that cannot forget.
/* weighted: each neighbour carries a cost */
const roads = new Map([
["home", [{ to: "shop", cost: 4 }, { to: "park", cost: 2 }]],
["park", [{ to: "shop", cost: 1 }]],
["shop", []],
]);
/* undirected: add both directions when you build it */
function connect(graph, a, b, cost = 1) {
if (!graph.has(a)) graph.set(a, []);
if (!graph.has(b)) graph.set(b, []);
graph.get(a).push({ to: b, cost });
graph.get(b).push({ to: a, cost });
}What is secretly a graph
That last row is the useful habit: many problems that do not look like graphs become easy once you name the nodes and the edges. "What is a state, and what is one move?" is often the whole solution.
| Problem | Nodes | Edges |
|---|---|---|
| Routing and maps | Junctions | Roads, weighted by time |
Build systems, npm install | Packages | Dependencies — a DAG, and a cycle is an error |
| Spreadsheet recalculation | Cells | References — topological order |
| Social features | People | Follows — directed |
| A maze, a game board | Squares | Legal moves — unweighted |
| Word ladders, puzzle states | Every reachable state | One legal move |
| Module imports, deadlocks | Modules, locks | Requires, waits-for — find the cycle |
Degree, paths and components
- Degree — how many edges touch a node. In a directed graph, in-degree and out-degree separately; a node with in-degree 0 is a root of a dependency order.
- Path — a sequence of nodes joined by edges. A cycle is a path back to where it started.
- Connected component — a group where everyone can reach everyone. "How many separate islands are there" is exactly this.
- Topological order — for a DAG, an order where every node comes after everything it depends on. That is what a build system computes.