Graph algorithms

2026-09-27

Traversals, grids, components, cycles, topological order, shortest paths and minimum spanning trees, in TypeScript, JavaScript and Python. Representations (adjacency list vs matrix), the typed MinHeap<T> and union-find are on Trees & graphs; the code here assumes that MinHeap (comparator constructor, push, pop, peek, size). Recursion and memoized search are on Recursion & DP.

Which algorithm?

$V$ = vertices (nodes), $E$ = edges.

Problem	Algorithm	Time	Space
Reachability, visit everything	BFS or DFS	$O(V + E)$	$O(V)$
Shortest path, unweighted (or all weights equal)	BFS	$O(V + E)$	$O(V)$
Shortest path, weights 0 or 1	0-1 BFS (deque)	$O(V + E)$	$O(V)$
Shortest path, weights ≥ 0	Dijkstra with a binary heap	$O((V + E) \log V)$	$O(V + E)$
Shortest path, negative weights; detect negative cycles	Bellman-Ford	$O(V E)$	$O(V)$
Shortest path in a DAG, any weights	relax edges in topological order	$O(V + E)$	$O(V)$
All pairs, $V$ up to a few hundred	Floyd-Warshall	$O(V^3)$	$O(V^2)$
Grid, unit moves	BFS on cells	$O(RC)$	$O(RC)$
Connected components (static)	BFS / DFS from each unvisited node	$O(V + E)$	$O(V)$
Components while edges arrive	union-find	$O(\alpha(V))$ per op, amortized	$O(V)$
Cycle, undirected	DFS with parent, or union-find	$O(V + E)$	$O(V)$
Cycle, directed	DFS with three colors, or Kahn leaves nodes	$O(V + E)$	$O(V)$
Order tasks with dependencies	topological sort (Kahn or DFS)	$O(V + E)$	$O(V)$
Two-coloring / bipartite	BFS or DFS coloring	$O(V + E)$	$O(V)$
Minimum spanning tree, sparse	Kruskal (sort + union-find)	$O(E \log E)$	$O(V + E)$
Minimum spanning tree, dense	Prim (array for dense graphs, heap otherwise)	$O(V^2)$ array, $O(E \log V)$ heap	$O(V + E)$
Point-to-point on a map or game grid	A* (Dijkstra plus a distance-to-goal estimate)	$\le$ Dijkstra	$O(V)$

$\alpha$ is the inverse Ackermann function: at most 4 for any input you will meet, so treat it as constant.

Setup

Nodes are 0..n-1 and the graph is an adjacency list: adj[u] holds the neighbors of u. Weighted graphs store [v, w] pairs. When nodes are strings, map them to indices first, or use a Map<string, string[]> / defaultdict(list).

type Edge = [number, number];
 
function buildAdj(
  n: number,
  edges: Edge[],
  directed = false,
): number[][] {
  const adj: number[][] = Array.from(
    { length: n },
    () => [],
  );
  for (const [u, v] of edges) {
    adj[u].push(v);
    if (!directed) adj[v].push(u);
  }
  return adj;
}

function buildAdj(n, edges, directed = false) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    if (!directed) adj[v].push(u);
  }
  return adj;
}

type Edge = tuple[int, int]
 
def build_adj(
    n: int, edges: list[Edge], directed: bool = False
) -> list[list[int]]:
    adj: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj

$O(V + E)$ time and space. Array(n).fill([]) and [[]] * n share one list between all nodes: build each list separately, as above.

BFS

Breadth-first search visits nodes in order of distance (edge count) from the source, so the first time it reaches a node is along a shortest path. It needs a FIFO queue.

Same graph, same start: BFS numbers nodes by distance, DFS by depth-first path.

// Edges from src to each node; -1 if unreachable
function bfs(adj: number[][], src: number): number[] {
  const dist = new Array<number>(adj.length).fill(-1);
  dist[src] = 0;
  const queue = [src];
  // head pointer: queue.shift() is O(n) per call
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    for (const v of adj[u]) {
      if (dist[v] !== -1) continue; // seen
      dist[v] = dist[u] + 1;
      queue.push(v);
    }
  }
  return dist;
}

// Edges from src to each node; -1 if unreachable
function bfs(adj, src) {
  const dist = new Array(adj.length).fill(-1);
  dist[src] = 0;
  const queue = [src];
  // head pointer: queue.shift() is O(n) per call
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    for (const v of adj[u]) {
      if (dist[v] !== -1) continue; // seen
      dist[v] = dist[u] + 1;
      queue.push(v);
    }
  }
  return dist;
}

from collections import deque
 
# Edges from src to each node; -1 if unreachable
def bfs(adj: list[list[int]], src: int) -> list[int]:
    dist = [-1] * len(adj)
    dist[src] = 0
    queue = deque([src])
    while queue:
        u = queue.popleft()  # O(1); list.pop(0) is O(n)
        for v in adj[u]:
            if dist[v] != -1:  # seen
                continue
            dist[v] = dist[u] + 1
            queue.append(v)
    return dist

$O(V + E)$ time, $O(V)$ space.

JavaScript has no built-in queue. Array.prototype.shift() moves every remaining element, so a BFS that shifts is $O(V^2)$ . Keep a head index into a growing array (as above), swap in a next array per level, or use the Deque<T> from Linear structures.
Mark a node as seen when you enqueue it, not when you dequeue it; otherwise it can enter the queue many times.
Need levels (e.g. "minutes", "moves")? Process the queue one level at a time: for (const u of level) building next, then level = next (see Rotting Oranges in Recipes).
To recover the path, store parent[v] = u when you set dist[v] and walk back from the target.

DFS

Depth-first search follows one path as far as it goes, then backtracks. Use it for reachability, components, cycle detection, topological order and backtracking; not for shortest paths.

function dfs(adj: number[][], src: number): number[] {
  const seen = new Set<number>();
  const order: number[] = [];
  const visit = (u: number): void => {
    seen.add(u);
    order.push(u); // preorder
    for (const v of adj[u]) {
      if (!seen.has(v)) visit(v);
    }
  };
  visit(src);
  return order;
}
 
// Same order, explicit stack: no recursion limit
function dfsIter(adj: number[][], src: number): number[] {
  const seen = new Set<number>();
  const order: number[] = [];
  const stack = [src];
  while (stack.length > 0) {
    const u = stack.pop()!;
    if (seen.has(u)) continue; // pushed twice
    seen.add(u);
    order.push(u);
    // reversed, so the first neighbor pops first
    for (const v of adj[u].toReversed()) {
      if (!seen.has(v)) stack.push(v);
    }
  }
  return order;
}

function dfs(adj, src) {
  const seen = new Set();
  const order = [];
  const visit = (u) => {
    seen.add(u);
    order.push(u); // preorder
    for (const v of adj[u]) {
      if (!seen.has(v)) visit(v);
    }
  };
  visit(src);
  return order;
}
 
// Same order, explicit stack: no recursion limit
function dfsIter(adj, src) {
  const seen = new Set();
  const order = [];
  const stack = [src];
  while (stack.length > 0) {
    const u = stack.pop();
    if (seen.has(u)) continue; // pushed twice
    seen.add(u);
    order.push(u);
    // reversed, so the first neighbor pops first
    for (const v of adj[u].toReversed()) {
      if (!seen.has(v)) stack.push(v);
    }
  }
  return order;
}

def dfs(adj: list[list[int]], src: int) -> list[int]:
    seen: set[int] = set()
    order: list[int] = []
 
    def visit(u: int) -> None:
        seen.add(u)
        order.append(u)  # preorder
        for v in adj[u]:
            if v not in seen:
                visit(v)
 
    visit(src)
    return order
 
# Same order, explicit stack: no recursion limit
def dfs_iter(adj: list[list[int]], src: int) -> list[int]:
    seen: set[int] = set()
    order: list[int] = []
    stack = [src]
    while stack:
        u = stack.pop()
        if u in seen:  # pushed twice
            continue
        seen.add(u)
        order.append(u)
        # reversed, so the first neighbor pops first
        stack.extend(v for v in reversed(adj[u])
                     if v not in seen)
    return order

$O(V + E)$ time, $O(V)$ space (seen set plus recursion or stack depth).

Detail	Rule
Visited structure	`Set` / `set` for any node type; a `boolean[]` (or `Uint8Array`) is faster for `0..n-1`
Recursion depth	a path graph of $10^5$ nodes overflows: Node/V8 allows about 10k frames, CPython 1,000 by default; use the iterative form
Iterative marking	mark on pop to match recursive order; mark on push for plain reachability (fewer stack entries, different order)
Preorder vs postorder	record before the loop (preorder) or after it (postorder: children finish first, used for topological sort)
Disconnected graph	loop over every node and start a search from each unvisited one

Grids as graphs

Each cell is a node; its neighbors are the adjacent cells that are in bounds and passable. Never build the adjacency list: generate neighbors on the fly.

Moves	Offsets `[dr, dc]`	Use
4 directions	`[1,0] [-1,0] [0,1] [0,-1]`	most grid problems (islands, mazes)
8 directions	the 4 plus `[1,1] [1,-1] [-1,1] [-1,-1]`	king moves, "Shortest Path in Binary Matrix"
Knight	`[±1,±2] [±2,±1]`	chess puzzles

"Number of Islands": count groups of 4-connected "1" cells. Each new unvisited land cell starts a flood fill that marks its whole island.

type Cell = [number, number];
const DIRS4: Cell[] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
 
function numIslands(grid: string[][]): number {
  const rows = grid.length;
  const cols = grid[0]?.length ?? 0;
  const seen = grid.map((row) => row.map(() => false));
  const isNewLand = (r: number, c: number): boolean =>
    r >= 0 && r < rows && c >= 0 && c < cols &&
    grid[r][c] === "1" && !seen[r][c];
 
  const flood = (r: number, c: number): void => {
    seen[r][c] = true;
    const stack: Cell[] = [[r, c]];
    while (stack.length > 0) {
      const [y, x] = stack.pop()!;
      for (const [dy, dx] of DIRS4) {
        if (!isNewLand(y + dy, x + dx)) continue;
        seen[y + dy][x + dx] = true;
        stack.push([y + dy, x + dx]);
      }
    }
  };
 
  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (!isNewLand(r, c)) continue;
      count++;
      flood(r, c);
    }
  }
  return count;
}

const DIRS4 = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];
 
function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0]?.length ?? 0;
  const seen = grid.map((row) => row.map(() => false));
  const isNewLand = (r, c) =>
    r >= 0 &&
    r < rows &&
    c >= 0 &&
    c < cols &&
    grid[r][c] === "1" &&
    !seen[r][c];
 
  const flood = (r, c) => {
    seen[r][c] = true;
    const stack = [[r, c]];
    while (stack.length > 0) {
      const [y, x] = stack.pop();
      for (const [dy, dx] of DIRS4) {
        if (!isNewLand(y + dy, x + dx)) continue;
        seen[y + dy][x + dx] = true;
        stack.push([y + dy, x + dx]);
      }
    }
  };
 
  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (!isNewLand(r, c)) continue;
      count++;
      flood(r, c);
    }
  }
  return count;
}

type Cell = tuple[int, int]
DIRS4: list[Cell] = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
def num_islands(grid: list[list[str]]) -> int:
    rows = len(grid)
    cols = len(grid[0]) if grid else 0
    seen = [[False] * cols for _ in range(rows)]
 
    def is_new_land(r: int, c: int) -> bool:
        return (0 <= r < rows and 0 <= c < cols
                and grid[r][c] == "1" and not seen[r][c])
 
    def flood(r: int, c: int) -> None:
        seen[r][c] = True
        stack: list[Cell] = [(r, c)]
        while stack:
            y, x = stack.pop()
            for dy, dx in DIRS4:
                if is_new_land(y + dy, x + dx):
                    seen[y + dy][x + dx] = True
                    stack.append((y + dy, x + dx))
 
    count = 0
    for r in range(rows):
        for c in range(cols):
            if is_new_land(r, c):
                count += 1
                flood(r, c)
    return count

$O(RC)$ time and space. Check bounds before indexing: in JS grid[-1] is undefined, so grid[-1][c] throws; in Python it silently wraps to the last row. Overwriting visited land with "0" saves the seen grid when mutating the input is allowed.

Components and cycles

Task	Undirected graph	Directed graph
Count components	start a BFS/DFS from each unvisited node and count starts; or union every edge and count roots	"strongly connected" components need Tarjan or Kosaraju, $O(V + E)$
Detect a cycle	a seen neighbor that is not your parent; or an edge whose ends already share a union-find root	an edge back to a node still on the DFS path (gray), or Kahn's sort leaves nodes behind
Undirected tree check	connected and exactly $V - 1$ edges ("Graph Valid Tree")	n/a

Undirected cycle check with a parent pointer:

// Simple undirected graph: no self-loops or repeats
function hasCycle(adj: number[][]): boolean {
  const seen = new Array<boolean>(adj.length).fill(false);
  for (let s = 0; s < adj.length; s++) {
    if (seen[s]) continue;
    seen[s] = true;
    const stack: [number, number][] = [[s, -1]];
    while (stack.length > 0) {
      const [u, parent] = stack.pop()!;
      for (const v of adj[u]) {
        if (v === parent) continue; // the edge we came by
        if (seen[v]) return true; // a second way to v
        seen[v] = true;
        stack.push([v, u]);
      }
    }
  }
  return false;
}

// Simple undirected graph: no self-loops or repeats
function hasCycle(adj) {
  const seen = new Array(adj.length).fill(false);
  for (let s = 0; s < adj.length; s++) {
    if (seen[s]) continue;
    seen[s] = true;
    const stack = [[s, -1]];
    while (stack.length > 0) {
      const [u, parent] = stack.pop();
      for (const v of adj[u]) {
        if (v === parent) continue; // the edge we came by
        if (seen[v]) return true; // a second way to v
        seen[v] = true;
        stack.push([v, u]);
      }
    }
  }
  return false;
}

# Simple undirected graph: no self-loops or repeats
def has_cycle(adj: list[list[int]]) -> bool:
    seen = [False] * len(adj)
    for s in range(len(adj)):
        if seen[s]:
            continue
        seen[s] = True
        stack = [(s, -1)]  # (node, parent)
        while stack:
            u, parent = stack.pop()
            for v in adj[u]:
                if v == parent:  # the edge we came by
                    continue
                if seen[v]:      # a second way to v
                    return True
                seen[v] = True
                stack.append((v, u))
    return False

$O(V + E)$ time, $O(V)$ space. With union-find, process each edge (u, v): if find(u) === find(v) there is a cycle, else union(u, v). Directed graphs need colors instead: a neighbor that is merely "seen" may sit on a different branch. The DFS topological sort below doubles as the directed cycle check.

Topological sort

An order of a DAG (directed acyclic graph) where every edge u → v puts u before v: build steps, course prerequisites, spreadsheet recalculation. It exists exactly when the graph has no cycle.

	Kahn's algorithm (BFS)	DFS postorder
Idea	repeatedly take a node with in-degree 0	a node finishes after everything it points to; reverse the finish order
Cycle signal	fewer than $V$ nodes come out	an edge to a gray (in-progress) node
Extras	a min-heap instead of the queue gives the smallest order lexicographically; levels give "parallel semesters"	same colors detect directed cycles

// Kahn: order, or null if a cycle leaves nodes behind
function topoKahn(adj: number[][]): number[] | null {
  const indeg = new Array<number>(adj.length).fill(0);
  for (const vs of adj) for (const v of vs) indeg[v]++;
  const queue: number[] = [];
  indeg.forEach((d, u) => {
    if (d === 0) queue.push(u);
  });
  for (let head = 0; head < queue.length; head++) {
    for (const v of adj[queue[head]]) {
      indeg[v]--;
      if (indeg[v] === 0) queue.push(v);
    }
  }
  return queue.length === adj.length ? queue : null;
}

// Kahn: order, or null if a cycle leaves nodes behind
function topoKahn(adj) {
  const indeg = new Array(adj.length).fill(0);
  for (const vs of adj) for (const v of vs) indeg[v]++;
  const queue = [];
  indeg.forEach((d, u) => {
    if (d === 0) queue.push(u);
  });
  for (let head = 0; head < queue.length; head++) {
    for (const v of adj[queue[head]]) {
      indeg[v]--;
      if (indeg[v] === 0) queue.push(v);
    }
  }
  return queue.length === adj.length ? queue : null;
}

from collections import deque
 
# Kahn: order, or None if a cycle leaves nodes behind
def topo_kahn(adj: list[list[int]]) -> list[int] | None:
    indeg = [0] * len(adj)
    for vs in adj:
        for v in vs:
            indeg[v] += 1
    queue = deque(u for u, d in enumerate(indeg) if d == 0)
    order: list[int] = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == len(adj) else None

const WHITE = 0; // not visited
const GRAY = 1; // on the current DFS path
const BLACK = 2; // finished
 
// Reverse postorder, or null on a directed cycle
function topoDfs(adj: number[][]): number[] | null {
  const color = new Array<number>(adj.length).fill(WHITE);
  const post: number[] = [];
  const visit = (u: number): boolean => {
    color[u] = GRAY;
    for (const v of adj[u]) {
      if (color[v] === GRAY) return false; // back edge
      if (color[v] === WHITE && !visit(v)) return false;
    }
    color[u] = BLACK;
    post.push(u);
    return true;
  };
  for (let u = 0; u < adj.length; u++) {
    if (color[u] === WHITE && !visit(u)) return null;
  }
  return post.reverse();
}

const WHITE = 0; // not visited
const GRAY = 1; // on the current DFS path
const BLACK = 2; // finished
 
// Reverse postorder, or null on a directed cycle
function topoDfs(adj) {
  const color = new Array(adj.length).fill(WHITE);
  const post = [];
  const visit = (u) => {
    color[u] = GRAY;
    for (const v of adj[u]) {
      if (color[v] === GRAY) return false; // back edge
      if (color[v] === WHITE && !visit(v)) return false;
    }
    color[u] = BLACK;
    post.push(u);
    return true;
  };
  for (let u = 0; u < adj.length; u++) {
    if (color[u] === WHITE && !visit(u)) return null;
  }
  return post.reverse();
}

WHITE, GRAY, BLACK = 0, 1, 2  # new, on path, finished
 
# Reverse postorder, or None on a directed cycle
def topo_dfs(adj: list[list[int]]) -> list[int] | None:
    color = [WHITE] * len(adj)
    post: list[int] = []
 
    def visit(u: int) -> bool:
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:  # back edge
                return False
            if color[v] == WHITE and not visit(v):
                return False
        color[u] = BLACK
        post.append(u)
        return True
 
    for u in range(len(adj)):
        if color[u] == WHITE and not visit(u):
            return None
    return post[::-1]

Both $O(V + E)$ time, $O(V)$ space. Python also ships graphlib.TopologicalSorter (raises CycleError).

Dijkstra

Single-source shortest paths with non-negative weights. Pop the closest unfinished node from a min-heap, finalize it, relax its edges. JavaScript has no heap: this uses the MinHeap<T> from Trees & graphs.

// adj[u] = [v, weight][], weights >= 0
function dijkstra(
  adj: [number, number][][],
  src: number,
): number[] {
  const dist = new Array<number>(adj.length).fill(Infinity);
  dist[src] = 0;
  // entries [distance, node], closest first
  const heap = new MinHeap<[number, number]>(
    (a, b) => a[0] - b[0],
  );
  heap.push([0, src]);
  while (heap.size > 0) {
    const [d, u] = heap.pop()!;
    if (d > dist[u]) continue; // stale entry
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        heap.push([dist[v], v]);
      }
    }
  }
  return dist;
}

// adj[u] = [v, weight][], weights >= 0
function dijkstra(adj, src) {
  const dist = new Array(adj.length).fill(Infinity);
  dist[src] = 0;
  // entries [distance, node], closest first
  const heap = new MinHeap((a, b) => a[0] - b[0]);
  heap.push([0, src]);
  while (heap.size > 0) {
    const [d, u] = heap.pop();
    if (d > dist[u]) continue; // stale entry
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        heap.push([dist[v], v]);
      }
    }
  }
  return dist;
}

import heapq
from math import inf
 
# adj[u] = [(v, weight), ...], weights >= 0
def dijkstra(
    adj: list[list[tuple[int, int]]], src: int
) -> list[float]:
    dist = [inf] * len(adj)
    dist[src] = 0
    heap = [(0, src)]  # (distance, node), closest first
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:  # stale entry
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

$O((V + E) \log V)$ time, $O(V + E)$ space. Neither heap supports "decrease key", so push a new entry and skip stale ones on pop ("lazy deletion").

Why no negative edges: a popped node is final because any other route to it passes through nodes that are at least as far away, and non-negative edges can only add. One negative edge can make a later, longer-looking route shorter, and the answer is silently wrong. Adding a constant to every weight does not fix it: it penalizes paths with more edges.
Stop early when the target pops if you only need one destination.
To get the path, record parent[v] = u on each successful relaxation.
Variants: "Network Delay Time" (max of dist), "Path With Minimum Effort" (the path cost is the max edge, not the sum; same loop), "Cheapest Flights Within K Stops" (state is (node, stops), or Bellman-Ford with $k + 1$ rounds).

Other shortest paths

Algorithm	Handles	Idea	Time
0-1 BFS	weights 0 or 1	a deque: push weight-0 neighbors to the front, weight-1 to the back; stays sorted like Dijkstra's heap	$O(V + E)$
Bellman-Ford	negative weights	relax every edge $V - 1$ times; a $V$ -th round that still improves means a negative cycle	$O(V E)$
SPFA	negative weights	Bellman-Ford with a queue of changed nodes; faster on average, same worst case	$O(V E)$
DAG relaxation	any weights, no cycles	relax edges in topological order; negate weights for the longest path	$O(V + E)$
Floyd-Warshall	all pairs, negatives	allow intermediate nodes `0..k` one at a time; `k` must be the outer loop	$O(V^3)$

type WEdge = [number, number, number]; // [u, v, w]
 
// null if a negative cycle is reachable from src
function bellmanFord(
  n: number,
  edges: WEdge[],
  src: number,
): number[] | null {
  const dist = new Array<number>(n).fill(Infinity);
  dist[src] = 0;
  for (let round = 0; round < n - 1; round++) {
    let changed = false;
    for (const [u, v, w] of edges) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        changed = true;
      }
    }
    if (!changed) break; // settled early
  }
  for (const [u, v, w] of edges) {
    if (dist[u] + w < dist[v]) return null;
  }
  return dist;
}

// [u, v, w]
 
// null if a negative cycle is reachable from src
function bellmanFord(n, edges, src) {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  for (let round = 0; round < n - 1; round++) {
    let changed = false;
    for (const [u, v, w] of edges) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        changed = true;
      }
    }
    if (!changed) break; // settled early
  }
  for (const [u, v, w] of edges) {
    if (dist[u] + w < dist[v]) return null;
  }
  return dist;
}

from math import inf
 
type WEdge = tuple[int, int, int]  # (u, v, w)
 
# None if a negative cycle is reachable from src
def bellman_ford(
    n: int, edges: list[WEdge], src: int
) -> list[float] | None:
    dist = [inf] * n
    dist[src] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:  # settled early
            break
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None
    return dist

// d: n×n, Infinity if no edge, 0 on the diagonal
function floydWarshall(d0: number[][]): number[][] {
  const d = d0.map((row) => row.slice());
  const n = d.length;
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        const viaK = d[i][k] + d[k][j];
        if (viaK < d[i][j]) d[i][j] = viaK;
      }
    }
  }
  return d; // d[i][i] < 0: i is on a negative cycle
}

// d: n×n, Infinity if no edge, 0 on the diagonal
function floydWarshall(d0) {
  const d = d0.map((row) => row.slice());
  const n = d.length;
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        const viaK = d[i][k] + d[k][j];
        if (viaK < d[i][j]) d[i][j] = viaK;
      }
    }
  }
  return d; // d[i][i] < 0: i is on a negative cycle
}

type Matrix = list[list[float]]
 
# d: n×n, inf if no edge, 0 on the diagonal
def floyd_warshall(d0: Matrix) -> Matrix:
    d = [row[:] for row in d0]
    n = len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                via_k = d[i][k] + d[k][j]
                if via_k < d[i][j]:
                    d[i][j] = via_k
    return d  # d[i][i] < 0: i is on a negative cycle

Minimum spanning tree

The cheapest set of edges that connects every node of a connected, undirected, weighted graph ( $V - 1$ edges, no cycles). Both algorithms are greedy: the lightest edge crossing any cut is safe to take.

	Kruskal	Prim
Grows	a forest; merges trees	one tree from a start node
Needs	edges sorted by weight, union-find	adjacency list, min-heap
Time	$O(E \log E)$	$O(E \log V)$ ; $O(V^2)$ with an array for dense graphs
Pick when	you have an edge list; sparse graphs	you have adjacency; dense graphs; points on a plane

Kruskal inlines a minimal union-find (path halving, no size tracking); the full UnionFind with union by size is on Trees & graphs.

// edges [u, v, w]; total MST weight, or null if the
// graph is disconnected
function kruskal(
  n: number,
  edges: [number, number, number][],
): number | null {
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  };
  let total = 0;
  let used = 0;
  const byWeight = edges.toSorted((a, b) => a[2] - b[2]);
  for (const [u, v, w] of byWeight) {
    const ru = find(u);
    const rv = find(v);
    if (ru === rv) continue; // would close a cycle
    parent[ru] = rv;
    total += w;
    used++;
  }
  return used === n - 1 ? total : null;
}

// edges [u, v, w]; total MST weight, or null if the
// graph is disconnected
function kruskal(n, edges) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x) => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  };
  let total = 0;
  let used = 0;
  const byWeight = edges.toSorted((a, b) => a[2] - b[2]);
  for (const [u, v, w] of byWeight) {
    const ru = find(u);
    const rv = find(v);
    if (ru === rv) continue; // would close a cycle
    parent[ru] = rv;
    total += w;
    used++;
  }
  return used === n - 1 ? total : null;
}

# edges (u, v, w); total MST weight, or None if the
# graph is disconnected
def kruskal(
    n: int, edges: list[tuple[int, int, int]]
) -> int | None:
    parent = list(range(n))
 
    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path halving
            x = parent[x]
        return x
 
    total = used = 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        ru, rv = find(u), find(v)
        if ru == rv:  # would close a cycle
            continue
        parent[ru] = rv
        total += w
        used += 1
    return total if used == n - 1 else None

// adj[u] = [v, w][] (undirected); MST weight from 0
function prim(adj: [number, number][][]): number {
  const inTree = new Array<boolean>(adj.length).fill(false);
  // entries [edge weight, node]
  const heap = new MinHeap<[number, number]>(
    (a, b) => a[0] - b[0],
  );
  heap.push([0, 0]);
  let total = 0;
  while (heap.size > 0) {
    const [w, u] = heap.pop()!;
    if (inTree[u]) continue; // stale entry
    inTree[u] = true;
    total += w;
    for (const [v, wv] of adj[u]) {
      if (!inTree[v]) heap.push([wv, v]);
    }
  }
  return total;
}

// adj[u] = [v, w][] (undirected); MST weight from 0
function prim(adj) {
  const inTree = new Array(adj.length).fill(false);
  // entries [edge weight, node]
  const heap = new MinHeap((a, b) => a[0] - b[0]);
  heap.push([0, 0]);
  let total = 0;
  while (heap.size > 0) {
    const [w, u] = heap.pop();
    if (inTree[u]) continue; // stale entry
    inTree[u] = true;
    total += w;
    for (const [v, wv] of adj[u]) {
      if (!inTree[v]) heap.push([wv, v]);
    }
  }
  return total;
}

import heapq
 
# adj[u] = [(v, w), ...] (undirected); MST weight from 0
def prim(adj: list[list[tuple[int, int]]]) -> int:
    in_tree = [False] * len(adj)
    heap = [(0, 0)]  # (edge weight, node)
    total = 0
    while heap:
        w, u = heapq.heappop(heap)
        if in_tree[u]:  # stale entry
            continue
        in_tree[u] = True
        total += w
        for v, wv in adj[u]:
            if not in_tree[v]:
                heapq.heappush(heap, (wv, v))
    return total

"Min Cost to Connect All Points" is Prim on a complete graph: use the $O(V^2)$ array version (no heap) since $E \approx V^2$ .

Recipes

Shortest path in a grid

BFS over cells; dist doubles as the visited mark. "Shortest Path in Binary Matrix" (8 directions, 0 is open, count cells on the path). $O(n^2)$ time and space.

type Cell = [number, number];
const DIRS8: Cell[] = [
  [1, 0], [-1, 0], [0, 1], [0, -1],
  [1, 1], [1, -1], [-1, 1], [-1, -1],
];
 
// Cells on the shortest path from top-left to
// bottom-right of an n×n grid, or -1
function shortestPathGrid(grid: number[][]): number {
  const n = grid.length;
  if (grid[0][0] !== 0 || grid[n - 1][n - 1] !== 0) {
    return -1;
  }
  const dist = grid.map((row) => row.map(() => 0));
  dist[0][0] = 1; // 0 means unvisited
  const queue: Cell[] = [[0, 0]];
  for (let head = 0; head < queue.length; head++) {
    const [r, c] = queue[head];
    if (r === n - 1 && c === n - 1) return dist[r][c];
    for (const [dr, dc] of DIRS8) {
      const y = r + dr;
      const x = c + dc;
      if (y < 0 || y >= n || x < 0 || x >= n) continue;
      if (grid[y][x] !== 0 || dist[y][x] !== 0) continue;
      dist[y][x] = dist[r][c] + 1;
      queue.push([y, x]);
    }
  }
  return -1;
}

const DIRS8 = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
  [1, 1],
  [1, -1],
  [-1, 1],
  [-1, -1],
];
 
// Cells on the shortest path from top-left to
// bottom-right of an n×n grid, or -1
function shortestPathGrid(grid) {
  const n = grid.length;
  if (grid[0][0] !== 0 || grid[n - 1][n - 1] !== 0) {
    return -1;
  }
  const dist = grid.map((row) => row.map(() => 0));
  dist[0][0] = 1; // 0 means unvisited
  const queue = [[0, 0]];
  for (let head = 0; head < queue.length; head++) {
    const [r, c] = queue[head];
    if (r === n - 1 && c === n - 1) return dist[r][c];
    for (const [dr, dc] of DIRS8) {
      const y = r + dr;
      const x = c + dc;
      if (y < 0 || y >= n || x < 0 || x >= n) continue;
      if (grid[y][x] !== 0 || dist[y][x] !== 0) continue;
      dist[y][x] = dist[r][c] + 1;
      queue.push([y, x]);
    }
  }
  return -1;
}

from collections import deque
 
type Cell = tuple[int, int]
DIRS8: list[Cell] = [
    (1, 0), (-1, 0), (0, 1), (0, -1),
    (1, 1), (1, -1), (-1, 1), (-1, -1),
]
 
# Cells on the shortest path from top-left to
# bottom-right of an n×n grid, or -1
def shortest_path_grid(grid: list[list[int]]) -> int:
    n = len(grid)
    if grid[0][0] != 0 or grid[n - 1][n - 1] != 0:
        return -1
    dist = [[0] * n for _ in range(n)]
    dist[0][0] = 1  # 0 means unvisited
    queue: deque[Cell] = deque([(0, 0)])
    while queue:
        r, c = queue.popleft()
        if (r, c) == (n - 1, n - 1):
            return dist[r][c]
        for dr, dc in DIRS8:
            y, x = r + dr, c + dc
            if not (0 <= y < n and 0 <= x < n):
                continue
            if grid[y][x] != 0 or dist[y][x] != 0:
                continue
            dist[y][x] = dist[r][c] + 1
            queue.append((y, x))
    return -1

If moves have different costs, switch to Dijkstra over cells; if the state includes more than the position (keys held, walls broken), make the state a tuple and the visited set cover it.

Multi-source BFS: Rotting Oranges

Start the queue with every source at distance 0; BFS then gives each cell its distance to the nearest source. Process level by level to count minutes. $O(RC)$ . Same idea: "Walls and Gates", "01 Matrix".

type Cell = [number, number];
const DIRS4: Cell[] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
 
// 2 = rotten, 1 = fresh, 0 = empty. Minutes until no
// fresh orange is left, or -1 if one never rots.
function orangesRotting(grid: number[][]): number {
  const g = grid.map((row) => row.slice());
  const rows = g.length;
  const cols = g[0]?.length ?? 0;
  let level: Cell[] = [];
  let fresh = 0;
  g.forEach((row, r) =>
    row.forEach((v, c) => {
      if (v === 2) level.push([r, c]);
      if (v === 1) fresh++;
    }),
  );
  let minutes = 0;
  while (level.length > 0 && fresh > 0) {
    const next: Cell[] = [];
    for (const [r, c] of level) {
      for (const [dr, dc] of DIRS4) {
        const y = r + dr;
        const x = c + dc;
        if (y < 0 || y >= rows || x < 0 || x >= cols) {
          continue;
        }
        if (g[y][x] !== 1) continue;
        g[y][x] = 2;
        fresh--;
        next.push([y, x]);
      }
    }
    level = next;
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

const DIRS4 = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];
 
// 2 = rotten, 1 = fresh, 0 = empty. Minutes until no
// fresh orange is left, or -1 if one never rots.
function orangesRotting(grid) {
  const g = grid.map((row) => row.slice());
  const rows = g.length;
  const cols = g[0]?.length ?? 0;
  let level = [];
  let fresh = 0;
  g.forEach((row, r) =>
    row.forEach((v, c) => {
      if (v === 2) level.push([r, c]);
      if (v === 1) fresh++;
    }),
  );
  let minutes = 0;
  while (level.length > 0 && fresh > 0) {
    const next = [];
    for (const [r, c] of level) {
      for (const [dr, dc] of DIRS4) {
        const y = r + dr;
        const x = c + dc;
        if (y < 0 || y >= rows || x < 0 || x >= cols) {
          continue;
        }
        if (g[y][x] !== 1) continue;
        g[y][x] = 2;
        fresh--;
        next.push([y, x]);
      }
    }
    level = next;
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

type Cell = tuple[int, int]
DIRS4: list[Cell] = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
# 2 = rotten, 1 = fresh, 0 = empty. Minutes until no
# fresh orange is left, or -1 if one never rots.
def oranges_rotting(grid: list[list[int]]) -> int:
    g = [row[:] for row in grid]
    rows, cols = len(g), len(g[0]) if g else 0
    level: list[Cell] = []
    fresh = 0
    for r, row in enumerate(g):
        for c, v in enumerate(row):
            if v == 2:
                level.append((r, c))
            elif v == 1:
                fresh += 1
    minutes = 0
    while level and fresh:
        nxt: list[Cell] = []
        for r, c in level:
            for dr, dc in DIRS4:
                y, x = r + dr, c + dc
                if not (0 <= y < rows and 0 <= x < cols):
                    continue
                if g[y][x] != 1:
                    continue
                g[y][x] = 2
                fresh -= 1
                nxt.append((y, x))
        level = nxt
        minutes += 1
    return minutes if fresh == 0 else -1

Course Schedule

Prerequisite pairs [course, before] are edges before → course. "Course Schedule" asks whether a topological order exists; "Course Schedule II" asks for one. Reuses buildAdj and topoKahn from above. $O(V + E)$ .

function findOrder(
  n: number,
  prereqs: [number, number][],
): number[] {
  const edges = prereqs.map(
    ([course, before]): Edge => [before, course],
  );
  return topoKahn(buildAdj(n, edges, true)) ?? [];
}
 
const canFinish = (
  n: number,
  prereqs: [number, number][],
): boolean => findOrder(n, prereqs).length === n;

function findOrder(n, prereqs) {
  const edges = prereqs.map(([course, before]) => [
    before,
    course,
  ]);
  return topoKahn(buildAdj(n, edges, true)) ?? [];
}
 
const canFinish = (n, prereqs) =>
  findOrder(n, prereqs).length === n;

def find_order(
    n: int, prereqs: list[tuple[int, int]]
) -> list[int]:
    edges = [(before, course) for course, before in prereqs]
    return topo_kahn(build_adj(n, edges, True)) or []
 
def can_finish(
    n: int, prereqs: list[tuple[int, int]]
) -> bool:
    return len(find_order(n, prereqs)) == n

Is it bipartite?

Color each component with BFS, alternating 0 and 1; an edge between equal colors means an odd cycle, so no two-coloring exists ("Is Graph Bipartite?", "Possible Bipartition"). $O(V + E)$ .

function isBipartite(adj: number[][]): boolean {
  const color = new Array<number>(adj.length).fill(-1);
  for (let s = 0; s < adj.length; s++) {
    if (color[s] !== -1) continue;
    color[s] = 0;
    const queue = [s];
    for (let head = 0; head < queue.length; head++) {
      const u = queue[head];
      for (const v of adj[u]) {
        if (color[v] === color[u]) return false;
        if (color[v] === -1) {
          color[v] = 1 - color[u];
          queue.push(v);
        }
      }
    }
  }
  return true;
}

function isBipartite(adj) {
  const color = new Array(adj.length).fill(-1);
  for (let s = 0; s < adj.length; s++) {
    if (color[s] !== -1) continue;
    color[s] = 0;
    const queue = [s];
    for (let head = 0; head < queue.length; head++) {
      const u = queue[head];
      for (const v of adj[u]) {
        if (color[v] === color[u]) return false;
        if (color[v] === -1) {
          color[v] = 1 - color[u];
          queue.push(v);
        }
      }
    }
  }
  return true;
}

from collections import deque
 
def is_bipartite(adj: list[list[int]]) -> bool:
    color = [-1] * len(adj)
    for s in range(len(adj)):
        if color[s] != -1:
            continue
        color[s] = 0
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if color[v] == color[u]:
                    return False
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    queue.append(v)
    return True

Reconstruct the shortest path

BFS with a parent array, then walk back from the target and reverse. Works the same after Dijkstra. $O(V + E)$ .

// Nodes from s to t inclusive; [] if unreachable
function shortestPath(
  adj: number[][],
  s: number,
  t: number,
): number[] {
  const parent = new Array<number>(adj.length).fill(-1);
  const seen = new Array<boolean>(adj.length).fill(false);
  seen[s] = true;
  const queue = [s];
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    if (u === t) break;
    for (const v of adj[u]) {
      if (seen[v]) continue;
      seen[v] = true;
      parent[v] = u;
      queue.push(v);
    }
  }
  if (!seen[t]) return [];
  const path: number[] = [];
  for (let v = t; v !== -1; v = parent[v]) path.push(v);
  return path.reverse();
}

// Nodes from s to t inclusive; [] if unreachable
function shortestPath(adj, s, t) {
  const parent = new Array(adj.length).fill(-1);
  const seen = new Array(adj.length).fill(false);
  seen[s] = true;
  const queue = [s];
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    if (u === t) break;
    for (const v of adj[u]) {
      if (seen[v]) continue;
      seen[v] = true;
      parent[v] = u;
      queue.push(v);
    }
  }
  if (!seen[t]) return [];
  const path = [];
  for (let v = t; v !== -1; v = parent[v]) path.push(v);
  return path.reverse();
}

from collections import deque
 
# Nodes from s to t inclusive; [] if unreachable
def shortest_path(
    adj: list[list[int]], s: int, t: int
) -> list[int]:
    parent = [-1] * len(adj)
    seen = [False] * len(adj)
    seen[s] = True
    queue = deque([s])
    while queue:
        u = queue.popleft()
        if u == t:
            break
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                queue.append(v)
    if not seen[t]:
        return []
    path: list[int] = []
    v = t
    while v != -1:
        path.append(v)
        v = parent[v]
    return path[::-1]

Network Delay Time

A signal leaves node k along weighted directed edges; how long until every node has it? That is the largest Dijkstra distance, or -1 if some node is unreachable. Reuses dijkstra from above. $O((V + E) \log V)$ .

// times: [from, to, ms], nodes numbered 1..n
function networkDelay(
  times: [number, number, number][],
  n: number,
  k: number,
): number {
  const adj: [number, number][][] = Array.from(
    { length: n + 1 },
    () => [],
  );
  for (const [u, v, w] of times) adj[u].push([v, w]);
  const dist = dijkstra(adj, k).slice(1); // drop node 0
  const worst = Math.max(...dist);
  return worst === Infinity ? -1 : worst;
}

// times: [from, to, ms], nodes numbered 1..n
function networkDelay(times, n, k) {
  const adj = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) adj[u].push([v, w]);
  const dist = dijkstra(adj, k).slice(1); // drop node 0
  const worst = Math.max(...dist);
  return worst === Infinity ? -1 : worst;
}

from math import inf
 
# times: (from, to, ms), nodes numbered 1..n
def network_delay(
    times: list[tuple[int, int, int]], n: int, k: int
) -> int:
    adj: list[list[tuple[int, int]]] = [
        [] for _ in range(n + 1)
    ]
    for u, v, w in times:
        adj[u].append((v, w))
    worst = max(dijkstra(adj, k)[1:])  # drop node 0
    return -1 if worst == inf else int(worst)

References

CLRS, Introduction to Algorithms, part VI: BFS, DFS, topological sort, MST, Bellman-Ford, Dijkstra, Floyd-Warshall
Python collections.deque (opens in a new tab), heapq (opens in a new tab) and graphlib (opens in a new tab): queue, heap and a built-in topological sorter
MDN: Array.prototype.shift() (opens in a new tab): why shifting in a loop is linear per call
Python wiki: TimeComplexity (opens in a new tab): list.pop(0) vs deque.popleft()
cp-algorithms: graphs (opens in a new tab): BFS, 0-1 BFS, Dijkstra, Bellman-Ford, MST with proofs
Tech Interview Handbook: graph (opens in a new tab): interview checklist and practice list
NeetCode roadmap (opens in a new tab): graphs and advanced graphs practice
Red Blob Games: Introduction to A* (opens in a new tab): BFS, Dijkstra and A* on game maps, interactive