演算法

1type Edge = [number, number, number]; // [u, v, weight]
2 
3function find(parent: number[], x: number): number {
4  while (parent[x] !== x) {
5    parent[x] = parent[parent[x]];
6    x = parent[x];
7  }
8  return x;
9}
10 
11function kruskal(n: number, edges: Edge[]): Edge[] {
12  const sorted = [...edges].sort((a, b) => a[2] - b[2] || a[0] - b[0] || a[1] - b[1]);
13  const parent = Array.from({ length: n }, (_, i) => i);
14  const size = new Array(n).fill(1);
15  const tree: Edge[] = [];
16  for (const [u, v, w] of sorted) {
17    if (tree.length === n - 1) break;
18    let ru = find(parent, u), rv = find(parent, v);
19    if (ru === rv) continue;
20    if (size[ru] < size[rv]) [ru, rv] = [rv, ru];
21    parent[rv] = ru;
22    size[ru] += size[rv];
23    tree.push([u, v, w]);
24  }
25  return tree;
26}
27 
28type Entry = [number, number, number, number]; // [weight, seq, from, to]
29const before = (a: Entry, b: Entry) => a[0] < b[0] || (a[0] === b[0] && a[1] < b[1]);
30 
31class EdgeHeap {
32  private a: Entry[] = [];
33  get size() { return this.a.length; }
34  push(e: Entry) {
35    const a = this.a;
36    a.push(e);
37    for (let i = a.length - 1, p; i > 0 && before(a[i], a[(p = (i - 1) >> 1)]); i = p) [a[i], a[p]] = [a[p], a[i]];
38  }
39  pop(): Entry {
40    const a = this.a, top = a[0], last = a.pop()!;
41    if (a.length === 0) return top;
42    a[0] = last;
43    for (let i = 0; ; ) {
44      const l = 2 * i + 1, r = l + 1;
45      let m = i;
46      if (l < a.length && before(a[l], a[m])) m = l;
47      if (r < a.length && before(a[r], a[m])) m = r;
48      if (m === i) return top;
49      [a[i], a[m]] = [a[m], a[i]];
50      i = m;
51    }
52  }
53}
54 
55function prim(n: number, edges: Edge[]): Edge[] {
56  const adj: [number, number][][] = Array.from({ length: n }, () => []);
57  for (const [u, v, w] of edges) {
58    adj[u].push([v, w]);
59    adj[v].push([u, w]);
60  }
61  for (const list of adj) list.sort((a, b) => a[0] - b[0]);
62  const inTree = new Array(n).fill(false);
63  const heap = new EdgeHeap();
64  let seq = 0;
65  const add = (node: number) => {
66    inTree[node] = true;
67    for (const [to, w] of adj[node]) {
68      if (!inTree[to]) heap.push([w, seq++, node, to]);
69    }
70  };
71  add(0);
72  const tree: Edge[] = [];
73  while (heap.size > 0 && tree.length < n - 1) {
74    const [w, , from, to] = heap.pop();
75    if (inTree[to]) continue;
76    tree.push([from, to, w]);
77    add(to);
78  }
79  return tree;
80}