最小共通祖先

Lowest Common Ancestor, LCA, 最近共通祖先などといわれる。「共通祖先」で検索すると、生物進化方面の用語が混じって出てくる。

根付き木において、頂点 $a$ と頂点 $b$ を根に向かって辿っていった時、最初に合流する頂点のことを指す。

     1
    /  \
   2  3    5と6のLCAは2
  / \
 4 5       3と4のLCAは1
 |
 6          1と2のLCAは1

元は根付き木でなくても、適当な頂点を根としてLCAを求められるようにしておくと、様々な用途に使える。

  • 任意の2点間距離
  • 任意の2頂点を含む部分木の深さ、要素数、などの情報

解法

求め方は複数のアルゴリズム・実装が知られている。

  • Euler Tour + Range Minimum Query
    • セグメント木
    • Sparce Table
  • ダブリング
  • Schieber-Vishkin algorithm

EulerTour + RMQ

オイラーツアー

オイラーツアーは、深さ優先探索で通りかかった順番に頂点を記述する方法。$N-1$ 辺を行き帰りで2回ずつとおるので、出発点と合わせて長さ $2N-1$ の配列になる。

     0
    /  \   
   1  2    0, 1, 3, 5, 3, 1, 4, 1, 0, 2, 0
  / \
 3 4
 |
 5

この変換により、木の祖先・子孫関係をわかりやすい形(1次元配列)で持つことができるため、 1次元配列で扱える様々なデータ構造を利用できる。BIT、セグメント木、など。

オイラーツアーを用いたLCA

LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で各頂点が最初に現れた位置も記録していく。

  • eular_tour[i] = (d, v)
    • $i$ 番目に通りかかる頂点の(深さ, 頂点番号)
  • first_appear[v] = i
    • 頂点 $v$ がeular_tour上で初めて現れるindex
     0
    /  \   eular_tour = [d: 0, 1, 2, 3, 2, 1, 2, 1, 0, 1, 0
   1  2                v: 0, 1, 3, 5, 3, 1, 4, 1, 0, 2, 0]
  / \
 3 4     first_appear = [0, 1, 9, 2, 6, 3]
 |
 5

こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。

  • それぞれが eular_tour 上ではじめて現れるindex $a_i,b_i$ を取得する
    • $a_i \lt b_i$ と仮定する
  • euler_tour上で、区間 $[a_i, b_i]$ 内から、depthが最小となる頂点を取得する
  • そいつがLCAである(このような頂点はただ1つ存在する)
頂点(a, b) = (5, 4) のLCAを求める
  → ai = 3, bi = 6
eular_tour[3:6] = [(3, 5), (2, 3), (1, 1), (2, 4)]
この中で最小は (1, 1) なので、深さ1の頂点1がLCA

もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、eular_tour で管理するのは $d$ のみでよい。

区間最小値

ここで、区間の最小値を求めるクエリRmQが発生する。以下のアルゴリズムなどで解ける。

  • 平方分割
  • セグメント木
  • Sparce Table

ダブリング

各頂点から、1個先の親、2個先の親、4個先の親、8個先の親、…を記録していく。

  • double[v][k] = u
    • 頂点 $v$ から $2^k$ 個先の親の頂点番号 $u$
  • depth[v] = d
    • 頂点 $v$ の深さ $d$

$k$ が小さい方から順に全頂点を埋めていくと、$k$ を求める際には $k-1$ の結果を利用できる。 最も深い頂点が1発で根にたどり着けるような $k$ で止める。

$a,b$ の深さを合わせる

$b$ の方が深いとし、深さの差が38(2進数で 100110)だったとする。

立っているbitだけ頂点を遡っていく。0-indexedで1,2,5桁目が'1'なので、

b2 = double[b ][1]
b3 = double[b2][2]
b4 = double[b3][5] → これでb4とaで深さが揃った

以降 $b$ は $b_4$ のことを指すとする。

同階層ながら互いに異なる、最も浅い祖先を求める

$a,b$ から1発で根にたどり着けるような最小の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。

  • double[a][k] != double[b][k] なら
    • a ← double[a][k], b ← double[b][k]
  • 同じなら何もしない
  • k ← k-1

$k=0$ までやったら、$a,b$ の1つ親がLCM。

バリエーション

二分木におけるLCA

木の構造が定まっているので、bit演算で計算できる。手順はダブリングと似ている。

根を1とし、頂点 $x$ の子を頂点 $2x,2x+1$ とする。こうすると、頂点番号のbit長が、その頂点の深さと一致する。

  1. $a,b$ のbit長が異なる場合、長い方(深い方)を、短い方にあわせて右bitshiftする
    1. $b$ の方が長く、$a$ に合わせた結果を $b'$ とする
  2. 上位bitから、$a$ と $b'$ がどこまで一致するか見ていく。下から数えて $i$ 桁目で食い違ったとする
  3. $a$ を $i$ 桁 右bitshiftしたものが答え
    1            0001
   /  \          /    \
  2  3      0010     0011
  /\  /\      / \       / \
 4567  0100 0101 0110 0111

3と4のLCA
1. 4(0100)を3(0011)にあわせて2桁にする → (0010)
2. (0010)と(0011)を先頭から一致するまで見ていく。下1桁で食い違う
3. (0010)を1桁 右bitshiftした (0001) がLCA
本WebサイトはcookieをPHPのセッション識別および左欄目次の開閉状況記憶のために使用しています。同意できる方のみご覧ください。More information about cookies
programming_algorithm/graph_theory/lowest_common_ancestor.txt · 最終更新: 2019/12/04 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0