Graph

   Kratie --- Kampong Cham --- Phnom Penh --- Siem Reap
                                  |               |
                                Kampot        Battambang
                                  |
                                 Kep

const names = ["A", "B", "C"];
const matrix = names.map(() => names.map(() => 0));

matrix[0][1] = matrix[1][0] = 1; // A - B
matrix[1][2] = matrix[2][1] = 1; // B - C

console.log(matrix);
// [ [ 0, 1, 0 ], [ 1, 0, 1 ], [ 0, 1, 0 ] ]

const list = new Map<string, string[]>([
  ["A", ["B"]],
  ["B", ["A", "C"]],
  ["C", ["B"]],
]);

class Graph<T = string> {
  private adjacency = new Map<T, Map<T, number>>();

  constructor(private directed = false) {}

  addVertex(vertex: T): void {
    if (!this.adjacency.has(vertex)) this.adjacency.set(vertex, new Map());
  }

  addEdge(from: T, to: T, weight = 1): void {
    this.addVertex(from);
    this.addVertex(to);
    this.adjacency.get(from)!.set(to, weight);
    if (!this.directed) this.adjacency.get(to)!.set(from, weight);
  }

  hasEdge(from: T, to: T): boolean {
    return this.adjacency.get(from)?.has(to) ?? false;
  }

  vertices(): T[] {
    return [...this.adjacency.keys()];
  }

  neighbors(vertex: T): T[] {
    return [...(this.adjacency.get(vertex)?.keys() ?? [])];
  }
}

const roads = new Graph();
roads.addEdge("Phnom Penh", "Kampong Cham");
roads.addEdge("Phnom Penh", "Kampot");
roads.addEdge("Phnom Penh", "Siem Reap");
roads.addEdge("Kampong Cham", "Kratie");
roads.addEdge("Siem Reap", "Battambang");
roads.addEdge("Kampot", "Kep");

console.log(roads.neighbors("Phnom Penh"));
// [ 'Kampong Cham', 'Kampot', 'Siem Reap' ]
console.log(roads.hasEdge("Kep", "Kampot")); // true

bfs(start: T): T[] {
  if (!this.adjacency.has(start)) return [];

  const order: T[] = [];
  const seen = new Set<T>([start]);
  const queue: T[] = [start];

  for (let head = 0; head < queue.length; head++) {
    const vertex = queue[head];
    order.push(vertex);

    for (const next of this.neighbors(vertex)) {
      if (!seen.has(next)) {
        seen.add(next); // mark when you ADD it, not when you visit it
        queue.push(next);
      }
    }
  }
  return order;
}

console.log(roads.bfs("Phnom Penh").join(", "));
// Phnom Penh, Kampong Cham, Kampot, Siem Reap, Kratie, Kep, Battambang

dfs(start: T): T[] {
  const order: T[] = [];
  const seen = new Set<T>();

  const visit = (vertex: T): void => {
    seen.add(vertex);
    order.push(vertex);
    for (const next of this.neighbors(vertex)) {
      if (!seen.has(next)) visit(next);
    }
  };

  if (this.adjacency.has(start)) visit(start);
  return order;
}

console.log(roads.dfs("Phnom Penh").join(", "));
// Phnom Penh, Kampong Cham, Kratie, Kampot, Kep, Siem Reap, Battambang

shortestPath(from: T, to: T): T[] | null {
  if (!this.adjacency.has(from) || !this.adjacency.has(to)) return null;

  const cameFrom = new Map<T, T | null>([[from, null]]);
  const queue: T[] = [from];

  for (let head = 0; head < queue.length; head++) {
    const vertex = queue[head];
    if (vertex === to) break; // found it: no need to look further

    for (const next of this.neighbors(vertex)) {
      if (!cameFrom.has(next)) {
        cameFrom.set(next, vertex);
        queue.push(next);
      }
    }
  }

  if (!cameFrom.has(to)) return null; // never reached

  const path: T[] = [];
  for (
    let v: T | null | undefined = to;
    v !== null && v !== undefined;
    v = cameFrom.get(v)
  ) {
    path.push(v);
  }
  return path.reverse();
}

console.log(roads.shortestPath("Kep", "Battambang")?.join(" -> "));
// Kep -> Kampot -> Phnom Penh -> Siem Reap -> Battambang

console.log(roads.shortestPath("Kep", "Nowhere"));
// null

connectedComponents(): T[][] {
  const seen = new Set<T>();
  const groups: T[][] = [];

  for (const vertex of this.vertices()) {
    if (seen.has(vertex)) continue;
    const group = this.bfs(vertex);
    for (const v of group) seen.add(v);
    groups.push(group);
  }
  return groups;
}

const g = new Graph();
g.addEdge("a", "b");
g.addEdge("c", "d");
g.addEdge("d", "e");
g.addVertex("f"); // alone

console.log(g.connectedComponents());
// [ [ 'a', 'b' ], [ 'c', 'd', 'e' ], [ 'f' ] ]

install --> build --> test --> deploy
lint -----> build
build --------------------> deploy

hasCycle(): boolean {
  const state = new Map<T, "visiting" | "done">();

  const visit = (vertex: T): boolean => {
    state.set(vertex, "visiting");
    for (const next of this.neighbors(vertex)) {
      const s = state.get(next);
      if (s === "visiting") return true; // back to a vertex on our path
      if (s === undefined && visit(next)) return true;
    }
    state.set(vertex, "done");
    return false;
  };

  for (const vertex of this.vertices()) {
    if (!state.has(vertex) && visit(vertex)) return true;
  }
  return false;
}

topologicalSort(): T[] | null {
  const incoming = new Map<T, number>();
  for (const v of this.vertices()) incoming.set(v, 0);
  for (const v of this.vertices()) {
    for (const next of this.neighbors(v)) {
      incoming.set(next, incoming.get(next)! + 1);
    }
  }

  const ready: T[] = this.vertices().filter((v) => incoming.get(v) === 0);
  const order: T[] = [];

  for (let head = 0; head < ready.length; head++) {
    const vertex = ready[head];
    order.push(vertex);
    for (const next of this.neighbors(vertex)) {
      const left = incoming.get(next)! - 1;
      incoming.set(next, left);
      if (left === 0) ready.push(next);
    }
  }

  return order.length === this.adjacency.size ? order : null;
}

const tasks = new Graph(true);
tasks.addEdge("install", "build");
tasks.addEdge("lint", "build");
tasks.addEdge("build", "test");
tasks.addEdge("build", "deploy");
tasks.addEdge("test", "deploy");

console.log(tasks.topologicalSort());
// [ 'install', 'lint', 'build', 'test', 'deploy' ]
console.log(tasks.hasCycle()); // false

tasks.addEdge("deploy", "install"); // now deploy must precede install
console.log(tasks.topologicalSort()); // null
console.log(tasks.hasCycle());        // true

        4
   A -------- B
    \        / \
   1 \    2 /   \ 1
      \    /     \
        C -------- D
             5

const km = new Graph();
km.addEdge("A", "B", 4);
km.addEdge("A", "C", 1);
km.addEdge("C", "B", 2);
km.addEdge("B", "D", 1);
km.addEdge("C", "D", 5);

import { PriorityQueue } from "./priority-queue.ts";

dijkstra(start: T): Map<T, number> {
  const best = new Map<T, number>();
  const queue = new PriorityQueue<[T, number]>((a, b) => a[1] - b[1]);
  queue.push([start, 0]);

  while (!queue.isEmpty()) {
    const [vertex, cost] = queue.pop() as [T, number];
    if (best.has(vertex)) continue; // already settled with a cheaper cost

    best.set(vertex, cost);
    for (const [next, weight] of this.adjacency.get(vertex) ?? []) {
      if (!best.has(next)) queue.push([next, cost + weight]);
    }
  }
  return best;
}

console.log(km.dijkstra("A"));
// Map(4) { 'A' => 0, 'C' => 1, 'B' => 3, 'D' => 4 }

pop (A, 0): settle A=0. Push (B, 4) and (C, 1).
pop (C, 1): settle C=1. Push (B, 3) and (D, 6).
pop (B, 3): settle B=3. Push (D, 4).
pop (B, 4): B is already settled. Skip.
pop (D, 4): settle D=4.
pop (D, 6): D is already settled. Skip.

km.addVertex("Z");
console.log(km.dijkstra("A").has("Z")); // false

const grid = [
  ["1", "1", "0", "0"],
  ["1", "0", "0", "1"],
  ["0", "0", "1", "1"],
  ["0", "0", "0", "0"],
];

function countIslands(grid: string[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const seen = new Set<string>();
  let islands = 0;

  const sink = (r: number, c: number): void => {
    if (r < 0 || c < 0 || r >= rows || c >= cols) return;
    if (grid[r][c] === "0" || seen.has(`${r},${c}`)) return;
    seen.add(`${r},${c}`);
    sink(r + 1, c);
    sink(r - 1, c);
    sink(r, c + 1);
    sink(r, c - 1);
  };

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1" && !seen.has(`${r},${c}`)) {
        islands++; // a new, unseen piece of land: a new island
        sink(r, c); // mark all of it as seen
      }
    }
  }
  return islands;
}

console.log(countIslands(grid)); // 2

function canFinish(count: number, prerequisites: [number, number][]): boolean {
  const g = new Graph<number>(true);
  for (let i = 0; i < count; i++) g.addVertex(i);
  for (const [course, before] of prerequisites) g.addEdge(before, course);
  return g.topologicalSort() !== null;
}

console.log(canFinish(2, [[1, 0]]));         // true  (take 0, then 1)
console.log(canFinish(2, [[1, 0], [0, 1]])); // false (each needs the other)

function shortestMaze(maze: string[]): number {
  const rows = maze.length;
  const cols = maze[0].length;
  let start = [0, 0];
  let end = [0, 0];

  maze.forEach((row, r) =>
    [...row].forEach((ch, c) => {
      if (ch === "S") start = [r, c];
      if (ch === "E") end = [r, c];
    }),
  );

  const dist = new Map<string, number>([[start.join(), 0]]);
  const queue = [start];

  for (let head = 0; head < queue.length; head++) {
    const [r, c] = queue[head];
    const here = dist.get(`${r},${c}`)!;
    if (r === end[0] && c === end[1]) return here;

    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr;
      const nc = c + dc;
      const key = `${nr},${nc}`;
      if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
      if (maze[nr][nc] === "#" || dist.has(key)) continue;
      dist.set(key, here + 1);
      queue.push([nr, nc]);
    }
  }
  return -1; // no way out
}

console.log(shortestMaze(["S.#.", "..#E", "...."])); // 6
console.log(shortestMaze(["S#E"]));                  // -1

import { PriorityQueue } from "./priority-queue.ts";

export class Graph<T = string> {
  private adjacency = new Map<T, Map<T, number>>();

  constructor(private directed = false) {}

  addVertex(vertex: T): void {
    if (!this.adjacency.has(vertex)) this.adjacency.set(vertex, new Map());
  }

  addEdge(from: T, to: T, weight = 1): void {
    this.addVertex(from);
    this.addVertex(to);
    this.adjacency.get(from)!.set(to, weight);
    if (!this.directed) this.adjacency.get(to)!.set(from, weight);
  }

  hasEdge(from: T, to: T): boolean {
    return this.adjacency.get(from)?.has(to) ?? false;
  }

  vertices(): T[] {
    return [...this.adjacency.keys()];
  }

  neighbors(vertex: T): T[] {
    return [...(this.adjacency.get(vertex)?.keys() ?? [])];
  }

  // Visit everything reachable from start, nearest first.
  bfs(start: T): T[] {
    if (!this.adjacency.has(start)) return [];
    const order: T[] = [];
    const seen = new Set<T>([start]);
    const queue: T[] = [start];
    for (let head = 0; head < queue.length; head++) {
      const vertex = queue[head];
      order.push(vertex);
      for (const next of this.neighbors(vertex)) {
        if (!seen.has(next)) {
          seen.add(next);
          queue.push(next);
        }
      }
    }
    return order;
  }

  // Visit everything reachable from start, going as deep as possible first.
  dfs(start: T): T[] {
    const order: T[] = [];
    const seen = new Set<T>();
    const visit = (vertex: T): void => {
      seen.add(vertex);
      order.push(vertex);
      for (const next of this.neighbors(vertex)) {
        if (!seen.has(next)) visit(next);
      }
    };
    if (this.adjacency.has(start)) visit(start);
    return order;
  }

  // Fewest-edges path from a to b, or null if b is unreachable.
  shortestPath(from: T, to: T): T[] | null {
    if (!this.adjacency.has(from) || !this.adjacency.has(to)) return null;
    const cameFrom = new Map<T, T | null>([[from, null]]);
    const queue: T[] = [from];
    for (let head = 0; head < queue.length; head++) {
      const vertex = queue[head];
      if (vertex === to) break;
      for (const next of this.neighbors(vertex)) {
        if (!cameFrom.has(next)) {
          cameFrom.set(next, vertex);
          queue.push(next);
        }
      }
    }
    if (!cameFrom.has(to)) return null;
    const path: T[] = [];
    for (
      let v: T | null | undefined = to;
      v !== null && v !== undefined;
      v = cameFrom.get(v)
    ) {
      path.push(v);
    }
    return path.reverse();
  }

  // Groups of vertices that can reach each other (undirected graphs).
  connectedComponents(): T[][] {
    const seen = new Set<T>();
    const groups: T[][] = [];
    for (const vertex of this.vertices()) {
      if (seen.has(vertex)) continue;
      const group = this.bfs(vertex);
      for (const v of group) seen.add(v);
      groups.push(group);
    }
    return groups;
  }

  // Directed graphs: is there a loop you can follow forever?
  hasCycle(): boolean {
    const state = new Map<T, "visiting" | "done">();
    const visit = (vertex: T): boolean => {
      state.set(vertex, "visiting");
      for (const next of this.neighbors(vertex)) {
        const s = state.get(next);
        if (s === "visiting") return true;
        if (s === undefined && visit(next)) return true;
      }
      state.set(vertex, "done");
      return false;
    };
    for (const vertex of this.vertices()) {
      if (!state.has(vertex) && visit(vertex)) return true;
    }
    return false;
  }

  // Directed graphs: an order where every edge points forward.
  // Returns null when a cycle makes that impossible.
  topologicalSort(): T[] | null {
    const incoming = new Map<T, number>();
    for (const v of this.vertices()) incoming.set(v, 0);
    for (const v of this.vertices()) {
      for (const next of this.neighbors(v)) {
        incoming.set(next, incoming.get(next)! + 1);
      }
    }
    const ready: T[] = this.vertices().filter((v) => incoming.get(v) === 0);
    const order: T[] = [];
    for (let head = 0; head < ready.length; head++) {
      const vertex = ready[head];
      order.push(vertex);
      for (const next of this.neighbors(vertex)) {
        const left = incoming.get(next)! - 1;
        incoming.set(next, left);
        if (left === 0) ready.push(next);
      }
    }
    return order.length === this.adjacency.size ? order : null;
  }

  // Cheapest total weight from start to every reachable vertex.
  // Weights must not be negative.
  dijkstra(start: T): Map<T, number> {
    const best = new Map<T, number>();
    const queue = new PriorityQueue<[T, number]>((a, b) => a[1] - b[1]);
    queue.push([start, 0]);
    while (!queue.isEmpty()) {
      const [vertex, cost] = queue.pop() as [T, number];
      if (best.has(vertex)) continue; // already settled with a cheaper cost
      best.set(vertex, cost);
      for (const [next, weight] of this.adjacency.get(vertex) ?? []) {
        if (!best.has(next)) queue.push([next, cost + weight]);
      }
    }
    return best;
  }
}

import { test } from "node:test";
import assert from "node:assert/strict";
import { Graph } from "./graph.ts";

function cambodia(): Graph {
  const g = new Graph();
  g.addEdge("Phnom Penh", "Kampong Cham");
  g.addEdge("Phnom Penh", "Kampot");
  g.addEdge("Phnom Penh", "Siem Reap");
  g.addEdge("Kampong Cham", "Kratie");
  g.addEdge("Siem Reap", "Battambang");
  g.addEdge("Kampot", "Kep");
  return g;
}

test("undirected edges go both ways", () => {
  const g = new Graph();
  g.addEdge("A", "B");
  assert.equal(g.hasEdge("A", "B"), true);
  assert.equal(g.hasEdge("B", "A"), true);
});

test("directed edges go one way", () => {
  const g = new Graph(true);
  g.addEdge("A", "B");
  assert.equal(g.hasEdge("A", "B"), true);
  assert.equal(g.hasEdge("B", "A"), false);
});

test("bfs visits nearest first, dfs goes deep first", () => {
  const g = cambodia();
  assert.deepEqual(g.bfs("Phnom Penh"), [
    "Phnom Penh", "Kampong Cham", "Kampot", "Siem Reap",
    "Kratie", "Kep", "Battambang",
  ]);
  assert.deepEqual(g.dfs("Phnom Penh"), [
    "Phnom Penh", "Kampong Cham", "Kratie", "Kampot",
    "Kep", "Siem Reap", "Battambang",
  ]);
});

test("shortestPath finds the fewest hops", () => {
  const g = cambodia();
  assert.deepEqual(g.shortestPath("Kep", "Battambang"), [
    "Kep", "Kampot", "Phnom Penh", "Siem Reap", "Battambang",
  ]);
  assert.equal(g.shortestPath("Kep", "Nowhere"), null);
});

test("connectedComponents groups separate islands", () => {
  const g = new Graph();
  g.addEdge("a", "b");
  g.addEdge("c", "d");
  g.addEdge("d", "e");
  g.addVertex("f");
  assert.deepEqual(g.connectedComponents(), [["a", "b"], ["c", "d", "e"], ["f"]]);
});

test("topologicalSort orders tasks and detects cycles", () => {
  const g = new Graph(true);
  g.addEdge("install", "build");
  g.addEdge("lint", "build");
  g.addEdge("build", "test");
  g.addEdge("build", "deploy");
  g.addEdge("test", "deploy");
  assert.deepEqual(g.topologicalSort(), [
    "install", "lint", "build", "test", "deploy",
  ]);
  assert.equal(g.hasCycle(), false);

  g.addEdge("deploy", "install");
  assert.equal(g.topologicalSort(), null);
  assert.equal(g.hasCycle(), true);
});

test("dijkstra finds the cheapest route, not the fewest hops", () => {
  const g = new Graph();
  g.addEdge("A", "B", 4);
  g.addEdge("A", "C", 1);
  g.addEdge("C", "B", 2);
  g.addEdge("B", "D", 1);
  g.addEdge("C", "D", 5);
  g.addVertex("Z");

  const best = g.dijkstra("A");
  assert.equal(best.get("B"), 3);
  assert.equal(best.get("D"), 4);
  assert.equal(best.has("Z"), false);
});

npx tsx --test

export * from "./graph.ts";

import { Graph } from "./src/graph.ts";

const g = new Graph();
g.addEdge("Phnom Penh", "Kampong Cham");
g.addEdge("Phnom Penh", "Kampot");
g.addEdge("Phnom Penh", "Siem Reap");
g.addEdge("Kampong Cham", "Kratie");
g.addEdge("Siem Reap", "Battambang");
g.addEdge("Kampot", "Kep");

console.log("bfs:", g.bfs("Phnom Penh").join(", "));
console.log("dfs:", g.dfs("Phnom Penh").join(", "));
console.log("path:", g.shortestPath("Kep", "Battambang")?.join(" -> "));

const tasks = new Graph(true);
tasks.addEdge("install", "build");
tasks.addEdge("lint", "build");
tasks.addEdge("build", "test");
tasks.addEdge("build", "deploy");
tasks.addEdge("test", "deploy");
console.log("order:", tasks.topologicalSort()?.join(", "));
tasks.addEdge("deploy", "install");
console.log("cycle:", tasks.hasCycle());

const roads = new Graph();
roads.addEdge("A", "B", 4);
roads.addEdge("A", "C", 1);
roads.addEdge("C", "B", 2);
roads.addEdge("B", "D", 1);
roads.addEdge("C", "D", 5);
console.log("cheapest from A:", JSON.stringify([...roads.dijkstra("A")]));

npx tsx demo-graph.ts

bfs: Phnom Penh, Kampong Cham, Kampot, Siem Reap, Kratie, Kep, Battambang
dfs: Phnom Penh, Kampong Cham, Kratie, Kampot, Kep, Siem Reap, Battambang
path: Kep -> Kampot -> Phnom Penh -> Siem Reap -> Battambang
order: install, lint, build, test, deploy
cycle: true
cheapest from A: [["A",0],["C",1],["B",3],["D",4]]