Graph functions
Each snippet below is something you will reach for while solving graph problems. Skim the short description, then copy the TypeScript for adjacency lists, matrices, and walks.
Prefer Overview for how graphs work, and Problems for practice once problems are linked.
Building an adjacency list
Start from vertices and edges, then grow the map of neighbors.
Adjacency list
Map each vertex to the list of vertices it can reach in one hop.
type Graph = Map<number, number[]>;
// ——— empty graph ———
const g: Graph = new Map();
// ——— seed vertices with empty neighbor lists ———
for (const v of [0, 1, 2, 3]) {
g.set(v, []);
}
// ——— directed edge u → v ———
g.get(0)!.push(1);
g.get(0)!.push(2);
// g: 0 → [1, 2]From edge list
Turn a list of [from, to] pairs into an adjacency list.
type Edge = readonly [number, number];
function toAdjList(n: number, edges: readonly Edge[]): Map<number, number[]> {
const g = new Map<number, number[]>();
for (let v = 0; v < n; v++) g.set(v, []);
for (const [u, v] of edges) {
g.get(u)!.push(v);
}
return g;
}
const edges: Edge[] = [
[0, 1],
[0, 2],
[1, 2],
];
const g = toAdjList(3, edges);
// 0 → [1, 2], 1 → [2], 2 → []Undirected both ways
For undirected graphs, record the edge in both neighbor lists.
function addUndirected(
g: Map<number, number[]>,
u: number,
v: number,
): void {
if (!g.has(u)) g.set(u, []);
if (!g.has(v)) g.set(v, []);
g.get(u)!.push(v);
g.get(v)!.push(u); // both directions
}
const g = new Map<number, number[]>();
addUndirected(g, 0, 1);
addUndirected(g, 1, 2);
// 0 → [1], 1 → [0, 2], 2 → [1]Adjacency matrix
An n×n grid where cell [i][j] means “is there an edge from i to j?”
Build matrix
Allocate an n×n zero grid, then mark edges as 1 (or a weight).
function toMatrix(n: number, edges: readonly [number, number][]): number[][] {
const m = Array.from({ length: n }, () => new Array(n).fill(0));
for (const [u, v] of edges) {
m[u]![v] = 1;
}
return m;
}
const m = toMatrix(3, [
[0, 1],
[0, 2],
[1, 2],
]);
// m[0][1] === 1, m[1][0] === 0 (directed)Undirected matrix
Mark both [u][v] and [v][u] so the matrix stays symmetric.
function addUndirectedEdge(m: number[][], u: number, v: number): void {
m[u]![v] = 1;
m[v]![u] = 1;
}
const n = 3;
const m = Array.from({ length: n }, () => new Array(n).fill(0));
addUndirectedEdge(m, 0, 1);
addUndirectedEdge(m, 1, 2);
// m[0][1] === m[1][0] === 1Edge check O(1)
Ask whether an edge exists by reading one cell — no neighbor scan.
function hasEdge(m: number[][], u: number, v: number): boolean {
return m[u]![v] === 1;
}
hasEdge(m, 0, 1); // true
hasEdge(m, 2, 0); // falseDegree & neighbors
Count how many edges touch a vertex, or list who sits one hop away.
Neighbors
Read the adjacency-list row for a vertex.
function neighbors(g: Map<number, number[]>, v: number): number[] {
return g.get(v) ?? [];
}
const next = neighbors(g, 0); // e.g. [1, 2]
for (const u of next) {
// visit each neighbor once
}Out-degree
How many edges leave this vertex — the length of its neighbor list.
function outDegree(g: Map<number, number[]>, v: number): number {
return g.get(v)?.length ?? 0;
}
outDegree(g, 0); // 2 if 0 → [1, 2]In-degree
How many edges point into this vertex — scan every list (or keep a count).
function inDegree(g: Map<number, number[]>, v: number): number {
let count = 0;
for (const [, outs] of g) {
for (const u of outs) {
if (u === v) count += 1;
}
}
return count;
}
// ——— or maintain counts while building ———
const indeg = new Array(n).fill(0);
for (const [u, v] of edges) indeg[v]! += 1;Add vertex & edge
Grow the graph one vertex or one edge at a time.
Add vertex
Register a new key with an empty neighbor list.
function addVertex(g: Map<number, number[]>, v: number): void {
if (!g.has(v)) g.set(v, []);
}
addVertex(g, 4);
// g now has 4 → []Add directed edge
Append v to u’s neighbor list. Create u if it is missing.
function addEdge(g: Map<number, number[]>, u: number, v: number): void {
if (!g.has(u)) g.set(u, []);
if (!g.has(v)) g.set(v, []);
g.get(u)!.push(v);
}
addEdge(g, 2, 4); // 2 → […, 4]Remove edge
Drop one occurrence of v from u’s neighbor list.
function removeEdge(g: Map<number, number[]>, u: number, v: number): void {
const outs = g.get(u);
if (!outs) return;
const i = outs.indexOf(v);
if (i >= 0) outs.splice(i, 1);
}
removeEdge(g, 0, 2);BFS skeleton
Walk level by level with a queue — first visit is the shortest hop count.
BFS traverse
Visit every reachable vertex in breadth-first order from a start.
function bfs(g: Map<number, number[]>, start: number): number[] {
const seen = new Set<number>([start]);
const q = [start];
const order: number[] = [];
while (q.length > 0) {
const u = q.shift()!;
order.push(u);
for (const v of g.get(u) ?? []) {
if (seen.has(v)) continue;
seen.add(v);
q.push(v);
}
}
return order;
}
bfs(g, 0); // e.g. [0, 1, 2, 3]BFS distances
Record how many edges each vertex sits from the start.
function bfsDist(
g: Map<number, number[]>,
start: number,
): Map<number, number> {
const dist = new Map<number, number>([[start, 0]]);
const q = [start];
while (q.length > 0) {
const u = q.shift()!;
for (const v of g.get(u) ?? []) {
if (dist.has(v)) continue;
dist.set(v, dist.get(u)! + 1);
q.push(v);
}
}
return dist;
}DFS skeleton
Dive as deep as you can along one path, then backtrack — stack or recursion.
DFS recursive
Mark visited, then recurse into each unvisited neighbor.
function dfs(
g: Map<number, number[]>,
start: number,
): number[] {
const seen = new Set<number>();
const order: number[] = [];
function walk(u: number): void {
seen.add(u);
order.push(u);
for (const v of g.get(u) ?? []) {
if (!seen.has(v)) walk(v);
}
}
walk(start);
return order;
}DFS iterative
Same idea with an explicit stack — useful when recursion depth worries you.
function dfsIter(g: Map<number, number[]>, start: number): number[] {
const seen = new Set<number>();
const stack = [start];
const order: number[] = [];
while (stack.length > 0) {
const u = stack.pop()!;
if (seen.has(u)) continue;
seen.add(u);
order.push(u);
const outs = g.get(u) ?? [];
for (let i = outs.length - 1; i >= 0; i--) {
const v = outs[i]!;
if (!seen.has(v)) stack.push(v);
}
}
return order;
}