Topological Sort, Union-Find and Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34function topologicalSort(n, edges) {
  // edges are [from, to] meaning: from must come BEFORE to.
  const g = new Map();
  const inDegree = new Array(n).fill(0);
  for (let i = 0; i < n; i++) g.set(i, []);

  for (const [from, to] of edges) {
    g.get(from).push(to);
    inDegree[to]++;                       // one more thing blocking `to`
  }

  // Start with everything that has no prerequisites.
  const queue = [];
  for (let i = 0; i < n; i++) if (inDegree[i] === 0) queue.push(i);

  const order = [];
  let head = 0;
  while (head < queue.length) {
    const node = queue[head++];
    order.push(node);
    for (const next of g.get(node)) {
      inDegree[next]--;                   // this dependency is now satisfied
      if (inDegree[next] === 0) queue.push(next);   // nothing left blocking it
    }
  }

  // If we could not place everything, the leftovers are in a cycle.
  return order.length === n ? order : null;
}

console.log('chain 0→1→2:', topologicalSort(3, [[0,1],[1,2]]));
console.log('diamond:', topologicalSort(4, [[0,1],[0,2],[1,3],[2,3]]));
console.log('cycle:', topologicalSort(2, [[0,1],[1,0]]), '← null means impossible');
console.log('no edges:', topologicalSort(3, []));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28function courseOrder(numCourses, prerequisites) {
  // prerequisites[i] = [course, mustTakeFirst]
  const g = new Map();
  const inDeg = new Array(numCourses).fill(0);
  for (let i = 0; i < numCourses; i++) g.set(i, []);
  for (const [course, first] of prerequisites) {
    g.get(first).push(course);            // first → course
    inDeg[course]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) if (inDeg[i] === 0) queue.push(i);
  const order = [];
  let head = 0;
  while (head < queue.length) {
    const c = queue[head++];
    order.push(c);
    for (const next of g.get(c)) if (--inDeg[next] === 0) queue.push(next);
  }
  return order.length === numCourses ? order : [];
}

const canFinish = (n, prereqs) => courseOrder(n, prereqs).length === n;

console.log('order for 4 courses:', courseOrder(4, [[1,0],[2,0],[3,1],[3,2]]));
console.log('canFinish, no cycle:', canFinish(2, [[1,0]]));
console.log('canFinish, cycle:   ', canFinish(2, [[1,0],[0,1]]));
console.log('impossible returns []:', courseOrder(2, [[1,0],[0,1]]));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24function topoSortDFS(n, edges) {
  const g = new Map();
  for (let i = 0; i < n; i++) g.set(i, []);
  for (const [from, to] of edges) g.get(from).push(to);

  const state = new Array(n).fill(0);    // 0 unvisited, 1 in progress, 2 done
  const order = [];
  let hasCycle = false;

  const visit = (node) => {
    if (state[node] === 1) { hasCycle = true; return; }
    if (state[node] === 2) return;
    state[node] = 1;
    for (const next of g.get(node)) visit(next);
    state[node] = 2;
    order.push(node);                     // push AFTER children: postorder
  };

  for (let i = 0; i < n; i++) visit(i);
  return hasCycle ? null : order.reverse();   // reverse postorder is topological
}

console.log('DFS topo, diamond:', topoSortDFS(4, [[0,1],[0,2],[1,3],[2,3]]));
console.log('DFS topo, cycle:  ', topoSortDFS(2, [[0,1],[1,0]]));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49class UnionFind {
  #parent;
  #rank;
  #groups;

  constructor(n) {
    this.#parent = Array.from({ length: n }, (_, i) => i);   // everyone is their own root
    this.#rank = new Array(n).fill(0);
    this.#groups = n;
  }

  get groups() { return this.#groups; }

  /* Find the root, flattening the path on the way back up. */
  find(x) {
    while (this.#parent[x] !== x) {
      this.#parent[x] = this.#parent[this.#parent[x]];   // path compression
      x = this.#parent[x];
    }
    return x;
  }

  /* Merge two groups. Returns false if they were already joined. */
  union(a, b) {
    const rootA = this.find(a), rootB = this.find(b);
    if (rootA === rootB) return false;

    // Attach the shorter tree under the taller one, keeping depth small.
    if (this.#rank[rootA] < this.#rank[rootB]) this.#parent[rootA] = rootB;
    else if (this.#rank[rootA] > this.#rank[rootB]) this.#parent[rootB] = rootA;
    else { this.#parent[rootB] = rootA; this.#rank[rootA]++; }

    this.#groups--;
    return true;
  }

  connected(a, b) { return this.find(a) === this.find(b); }
}

const uf = new UnionFind(6);
console.log('groups at the start:', uf.groups);
uf.union(0, 1);
uf.union(2, 3);
console.log('after joining 0-1 and 2-3:', uf.groups, 'groups');
console.log('0 and 1 connected?', uf.connected(0, 1));
console.log('0 and 2 connected?', uf.connected(0, 2));
uf.union(1, 2);
console.log('after joining 1-2:', uf.groups, 'groups | 0 and 3 connected?', uf.connected(0, 3));
console.log('joining 0-3 again returns:', uf.union(0, 3), '← already together');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45class UnionFind {
  #p; #r; #g;
  constructor(n) { this.#p = Array.from({length: n}, (_, i) => i); this.#r = new Array(n).fill(0); this.#g = n; }
  get groups() { return this.#g; }
  find(x) { while (this.#p[x] !== x) { this.#p[x] = this.#p[this.#p[x]]; x = this.#p[x]; } return x; }
  union(a, b) { const ra = this.find(a), rb = this.find(b); if (ra === rb) return false;
    if (this.#r[ra] < this.#r[rb]) this.#p[ra] = rb; else if (this.#r[ra] > this.#r[rb]) this.#p[rb] = ra;
    else { this.#p[rb] = ra; this.#r[ra]++; } this.#g--; return true; }
  connected(a, b) { return this.find(a) === this.find(b); }
}

// 1. Count components: one line after the unions.
function countComponents(n, edges) {
  const uf = new UnionFind(n);
  for (const [a, b] of edges) uf.union(a, b);
  return uf.groups;
}
console.log('components:', countComponents(5, [[0,1],[1,2],[3,4]]));

// 2. Detect a cycle in an undirected graph: a union that was already joined.
function hasCycle(n, edges) {
  const uf = new UnionFind(n);
  for (const [a, b] of edges) if (!uf.union(a, b)) return true;
  return false;
}
console.log('tree has cycle:', hasCycle(3, [[0,1],[1,2]]));
console.log('triangle has cycle:', hasCycle(3, [[0,1],[1,2],[2,0]]));

// 3. Is it a valid tree? Connected AND no cycle: exactly n-1 edges, one group.
function isValidTree(n, edges) {
  if (edges.length !== n - 1) return false;
  const uf = new UnionFind(n);
  for (const [a, b] of edges) if (!uf.union(a, b)) return false;
  return uf.groups === 1;
}
console.log('valid tree:', isValidTree(5, [[0,1],[0,2],[0,3],[1,4]]));
console.log('has a cycle:', isValidTree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]));

// 4. The redundant connection: the first edge that closes a cycle.
function findRedundant(edges) {
  const uf = new UnionFind(edges.length + 1);
  for (const [a, b] of edges) if (!uf.union(a, b)) return [a, b];
  return [];
}
console.log('redundant edge:', findRedundant([[1,2],[1,3],[2,3]]));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class UnionFind {
  #p; #r;
  constructor(n) { this.#p = Array.from({length: n}, (_, i) => i); this.#r = new Array(n).fill(0); }
  find(x) { while (this.#p[x] !== x) { this.#p[x] = this.#p[this.#p[x]]; x = this.#p[x]; } return x; }
  union(a, b) { const ra = this.find(a), rb = this.find(b); if (ra === rb) return false;
    if (this.#r[ra] < this.#r[rb]) this.#p[ra] = rb; else if (this.#r[ra] > this.#r[rb]) this.#p[rb] = ra;
    else { this.#p[rb] = ra; this.#r[ra]++; } return true; }
}

// Connect every node at the lowest total cost. Sort edges cheapest first and
// take each one that does not create a cycle. That is the whole algorithm.
function minimumSpanningTree(n, weightedEdges) {
  const sorted = [...weightedEdges].sort((a, b) => a[2] - b[2]);
  const uf = new UnionFind(n);
  const chosen = [];
  let total = 0;

  for (const [a, b, weight] of sorted) {
    if (uf.union(a, b)) {              // no cycle: take it
      chosen.push([a, b, weight]);
      total += weight;
      if (chosen.length === n - 1) break;   // a spanning tree has n-1 edges
    }
  }
  return { total, chosen, connected: chosen.length === n - 1 };
}

console.log(minimumSpanningTree(4, [[0,1,1],[0,2,4],[1,2,2],[1,3,6],[2,3,3]]));
console.log(minimumSpanningTree(3, [[0,1,5]]), '← not connected');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25// 0 → 1 costs 10, 0 → 2 → 1 costs 1 + 1 = 2.
// BFS reaches 1 in one hop and wrongly calls that the best.
const weighted = new Map([
  [0, [[1, 10], [2, 1]]],
  [1, []],
  [2, [[1, 1]]],
]);

function bfsHops(start, goal, g) {
  const dist = new Map([[start, 0]]);
  const q = [start];
  let head = 0;
  while (head < q.length) {
    const node = q[head++];
    for (const [next] of g.get(node)) {
      if (dist.has(next)) continue;
      dist.set(next, dist.get(node) + 1);
      q.push(next);
    }
  }
  return dist.get(goal);
}

console.log('BFS says 0 → 1 takes', bfsHops(0, 1, weighted), 'hop(s) — true, but that is not the cost');
console.log('cheapest cost is actually 2, via node 2');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58class Heap {
  #a = []; #c;
  constructor(c) { this.#c = c; }
  get size() { return this.#a.length; }
  push(v) { this.#a.push(v); let i = this.#a.length - 1;
    while (i > 0) { const p = (i-1)>>1; if (this.#c(this.#a[p], this.#a[i]) <= 0) break;
      [this.#a[p], this.#a[i]] = [this.#a[i], this.#a[p]]; i = p; } return this; }
  pop() { const t = this.#a[0], l = this.#a.pop();
    if (this.#a.length) { this.#a[0] = l; let i = 0; const n = this.#a.length;
      while (true) { const L = 2*i+1, R = 2*i+2; let b = i;
        if (L < n && this.#c(this.#a[L], this.#a[b]) < 0) b = L;
        if (R < n && this.#c(this.#a[R], this.#a[b]) < 0) b = R;
        if (b === i) break; [this.#a[i], this.#a[b]] = [this.#a[b], this.#a[i]]; i = b; } }
    return t; }
}

function dijkstra(n, adjacency, source) {
  const dist = new Array(n).fill(Infinity);
  const prev = new Array(n).fill(null);
  dist[source] = 0;

  const heap = new Heap((a, b) => a[0] - b[0]);   // [distance, node]
  heap.push([0, source]);

  while (heap.size > 0) {
    const [d, node] = heap.pop();
    // Stale entry: we already found a better route to this node.
    if (d > dist[node]) continue;

    for (const [next, weight] of adjacency.get(node)) {
      const candidate = d + weight;
      if (candidate < dist[next]) {
        dist[next] = candidate;
        prev[next] = node;
        heap.push([candidate, next]);
      }
    }
  }
  return { dist, prev };
}

const g = new Map([
  [0, [[1, 4], [2, 1]]],
  [1, [[3, 1]]],
  [2, [[1, 2], [3, 5]]],
  [3, []],
]);

const { dist, prev } = dijkstra(4, g, 0);
console.log('cheapest cost from 0 to each node:', dist);

const path = [];
for (let n = 3; n !== null; n = prev[n]) path.push(n);
console.log('cheapest route to 3:', path.reverse(), '← cost', dist[3]);

// Unreachable nodes stay at Infinity.
const g2 = new Map([[0, [[1, 1]]], [1, []], [2, []]]);
console.log('with node 2 unreachable:', dijkstra(3, g2, 0).dist);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25function bellmanFord(n, edges, source) {
  const dist = new Array(n).fill(Infinity);
  dist[source] = 0;

  // Relax every edge n-1 times: enough for any shortest path.
  for (let round = 0; round < n - 1; round++) {
    let changed = false;
    for (const [from, to, w] of edges) {
      if (dist[from] !== Infinity && dist[from] + w < dist[to]) {
        dist[to] = dist[from] + w;
        changed = true;
      }
    }
    if (!changed) break;                 // settled early
  }

  // One more pass: any further improvement means a negative cycle.
  for (const [from, to, w] of edges) {
    if (dist[from] !== Infinity && dist[from] + w < dist[to]) return { dist: null, negativeCycle: true };
  }
  return { dist, negativeCycle: false };
}

console.log('with a negative edge:', bellmanFord(4, [[0,1,4],[0,2,5],[2,1,-3],[1,3,3]], 0));
console.log('negative cycle:', bellmanFord(3, [[0,1,1],[1,2,-2],[2,0,-2]], 0));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18function floydWarshall(n, edges) {
  const d = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
  for (const [a, b, w] of edges) d[a][b] = Math.min(d[a][b], w);

  // Try every node as an intermediate stop. The k loop MUST be outermost.
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];

  return d;
}

const result = floydWarshall(4, [[0,1,5],[1,2,3],[2,3,1],[0,3,10]]);
console.log('all-pairs shortest distances:');
result.forEach((row, i) => console.log(' from', i, '→', row.map(v => v === Infinity ? '∞' : v).join(' ')));
console.log('0 to 3 is', result[0][3], 'via 1 and 2, cheaper than the direct edge of 10');