【TypeScript】木構造でノードとノードの共通の先祖を見つける「LCA」

やりたいこと

この図を見てください。

8と10にとっての4など、二つのノードにとって最も近い共通の先祖をLCA(Lowest Common Ancestor)といいます。
このLCAを求めたいことがあります。

問題点

もちろん、普通に両方のノードから一個ずつ親を辿っていけば、いつかはLCAが見つかります。
しかし、この方法では要素数がとても多い場合効率が悪いです。

解決策

ダブリングという方法を使います。
まず先に、ある要素の1個上の親、2個上の親、4個上の親、8、16、32……と、
2を倍にしていった数だけ遡った祖先を求めて表にしておきます。

ちなみに、この表を作る計算量は少ないです。
例えば8個上の親を求めるために8回遡る必要はありません。
既に各頂点からの4個上の親が求まっているなら、既存の表から4個上の親の4個上の親を調べればいいだけです。
このように再帰的に計算していくことで効率よく表を構築できます。
表を作る計算量は頂点数*Log(頂点数)です。

この表があれば高速に木を遡ることができます。
例えば、11個上の親に行きたければ8 + 2 + 1ですね。

この表を使って両側から高速に遡ることでLCAを求めることができます。

コード

class LCA {
  private log: number;
  private depth: number[];
  private table: number[][];

  constructor(private tree: number[][]) {
    const n = tree.length;
    this.log = Math.ceil(Math.log2(n));
    this.table = new Array(this.log);
    for (let i = 0; i < this.log; i++) {
      this.table[i] = new Array(n);
      for (let j = 0; j < n; j++) {
        this.table[i][j] = -1;
      }
    }
    this.depth = new Array(n);
    this.build();
  }

  private dfs(index: number, parent: number, depth: number) {
    this.table[0][index] = parent;
    this.depth[index] = depth;
    for (const to of this.tree[index]) {
      if (to === parent) continue;
      this.dfs(to, index, depth + 1);
    }
  }

  public build() {
    this.dfs(0, -1, 0);
    for (let k = 0; k + 1 < this.log; k++) {
      for (let i = 0; i < this.table[k].length; i++) {
        if (this.table[k][i] == -1) this.table[k + 1][i] = -1;
        else this.table[k + 1][i] = this.table[k][this.table[k][i]];
      }
    }
  }

  public query(u: number, v: number) {
    if (this.depth[u] > this.depth[v]) return this.query(v, u);
    for (let i = this.log - 1; i >= 0; i--) {
      if (((this.depth[v] - this.depth[u]) >> i) & 1) v = this.table[i][v];
    }
    if (u === v) return u;
    for (let i = this.log - 1; i >= 0; i--) {
      if (this.table[i][u] !== this.table[i][v]) {
        u = this.table[i][u];
        v = this.table[i][v];
      }
    }
    return this.table[0][u];
  }
}

interface Line {
  from: number;
  to: number;
}

function main() {
  const lines: Line[] = [
    { from: 0, to: 1 },
    { from: 0, to: 4 },
    { from: 1, to: 2 },
    { from: 1, to: 3 },
    { from: 4, to: 5 },
    { from: 4, to: 6 },
    { from: 4, to: 7 },
    { from: 5, to: 8 },
    { from: 5, to: 9 },
    { from: 7, to: 10 },
    { from: 9, to: 11 },
  ];

  // tree[from] = [ to list ]
  const tree: number[][] = new Array(12);
  for (let i = 0; i < 12; i++) tree[i] = [];

  for (const l of lines) {
    tree[l.from].push(l.to);
  }

  const lca = new LCA(tree);

  console.log(lca.query(8, 10));
  console.log(lca.query(9, 2));
  console.log(lca.query(5, 11));
}

main();