差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:graph_theory:lowest_common_ancestor [2019/11/28] – [EulerTour + RMQ] ikatakos | programming_algorithm:graph_theory:lowest_common_ancestor [2020/05/10] – [ダブリング] ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
====== 最小共通祖先 ====== | ====== 最小共通祖先 ====== | ||
- | Lowest Common Ancestor, LCA, 最近共通祖先などといわれる。「共通祖先」で検索すると、生物進化方面の用語が混じって出てくる。 | + | Lowest Common Ancestor, LCA, 最近共通祖先などといわれる。「共通祖先」で検索すると生物進化方面の用語が混じって出てくるので記事をやや探しづらい。 |
* [[https:// | * [[https:// | ||
行 15: | 行 15: | ||
| | ||
- | 元は根付き木でなくても、適当な頂点を根としてLCAを求められるようにしておくと、様々な用途に使える。 | + | 元は根付き木でなくても、適当な頂点を根としてLCAを求められるようにしておくと、様々な用途に使える。(追加で前計算する情報が必要になる場合がある) |
* 任意の2点間距離 | * 任意の2点間距離 | ||
- | * 任意の2頂点を含む部分木の深さ、要素数、などの情報 | + | |
+ | | ||
行 26: | 行 27: | ||
* Euler Tour + Range Minimum Query | * Euler Tour + Range Minimum Query | ||
- | * セグメント木 | ||
- | * Sparce Table | ||
* ダブリング | * ダブリング | ||
* Schieber-Vishkin algorithm | * Schieber-Vishkin algorithm | ||
- | ==== EulerTour + RMQ ==== | + | ==== EulerTour + RmQ ==== |
- | オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で以下の情報も記録していく。 | + | ===オイラーツアー=== |
+ | |||
+ | オイラーツアーは、深さ優先探索で通りかかった順番に頂点を記述する方法。$N-1$ 辺を行き帰りで2回ずつとおるので、出発点と合わせて長さ $2N-1$ の配列になる。 | ||
+ | |||
+ | 0 | ||
+ | / \ | ||
+ | | ||
+ | / \ | ||
+ | 3 4 | ||
+ | | | ||
+ | 5 | ||
+ | |||
+ | この変換により、木の祖先・子孫関係を1次元配列で持つことができるため、 | ||
+ | 1次元配列で扱える様々なデータ構造を利用できる(BIT、セグメント木など) | ||
+ | |||
+ | ===オイラーツアーを用いたLCA=== | ||
+ | |||
+ | LCAを求めるには、オイラーツアーで通りかかった順番に頂点番号と深さを記録していく。 | ||
+ | また、その過程で各頂点が最初に現れた位置も記録していく。 | ||
+ | (実際には、最初に現れた位置でなく、最初~最後までのどこかの位置であればよいが、通常は最初に記録しておくのが一番やりやすい) | ||
* '' | * '' | ||
- | * $i = 0 ~ 2(N-1)$ について、$i$ 番目に通りかかる頂点の(深さ, | + | * $i$ 番目に通りかかる頂点の(深さ, |
- | * '' | + | |
- | * 頂点 $v$ の深さ | + | |
* '' | * '' | ||
* 頂点 $v$ がeular_tour上で初めて現れるindex | * 頂点 $v$ がeular_tour上で初めて現れるindex | ||
行 46: | 行 62: | ||
| | ||
/ \ | / \ | ||
- | 3 4 depth = [0, 1, 1, 2, 2, 3] | + | 3 4 first_appear |
- | | + | | |
5 | 5 | ||
こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。 | こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。 | ||
- | * '' | + | * それぞれが |
- | * $a_i \lt b_i$ と仮定する | + | * $p_a \lt p_b$ と仮定する |
- | * '' | + | * '' |
- | * そいつがLCAである | + | * そいつがLCAである(このような頂点はただ1つ存在する) |
- | 頂点5と4 | + | 頂点(a, b) = (5, 4) のLCAを求める |
+ | | ||
eular_tour[3: | eular_tour[3: | ||
- | この中で最小は (1, 1) なので、深さ1の頂点1がLCA | + | この中で最小は (1, 1) なので、深さ1の頂点「1」がLCA |
もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、'' | もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、'' | ||
+ | ===区間最小値=== | ||
ここで、区間の最小値を求めるクエリRmQが発生する。以下のアルゴリズムなどで解ける。 | ここで、区間の最小値を求めるクエリRmQが発生する。以下のアルゴリズムなどで解ける。 | ||
行 68: | 行 86: | ||
* 平方分割 | * 平方分割 | ||
* セグメント木 | * セグメント木 | ||
- | * Sparce | + | * Sparse |
+ | 基本的に更新は不要なので、前処理 $O(N \log{N})$、クエリ $O(1)$ で処理できるSparse Tableが高速。 | ||
==== ダブリング ==== | ==== ダブリング ==== | ||
- | 各頂点から、1個先の親、2個先の親、4個先の親、8個先の親、...を記録していく。 | + | ダブリングは、前計算で1個先、2個先、4個先、8個先、... |
- | | + | これをLCAを求めるのに適用する。 |
+ | |||
+ | 各頂点から、1個先の親、2個先の親、4個先の親、8個先の親、...を記録していく。(便宜的に根の親は根とする) | ||
+ | |||
+ | | ||
* 頂点 $v$ から $2^k$ 個先の親の頂点番号 $u$ | * 頂点 $v$ から $2^k$ 個先の親の頂点番号 $u$ | ||
* '' | * '' | ||
* 頂点 $v$ の深さ $d$ | * 頂点 $v$ の深さ $d$ | ||
- | $k$ が小さい方から順に全頂点を埋めていくと、$k$ を求める際には $k-1$ の結果を利用できる。 | + | $k$ が小さい方から順に全頂点を埋めていくと、$double[k][v]=double[k-1][double[k-1][v]]]$ と直前の結果を利用できる。 |
- | 最も深い頂点が1発で根にたどり着けるような $k$ で止める。 | + | 最も深い頂点が1発で根にたどり着くような $k$ で止める。 |
== $a,b$ の深さを合わせる == | == $a,b$ の深さを合わせる == | ||
- | $b$ の方が深いとし、深さの差が2進数で 100110 だったとする | + | 作業用の変数として $a_t,b_t$ を用意し、$a_t←a$、$b_t←b$ |
- | 先頭のbitから頂点を遡っていく | + | $b_t$ の方が深いとし、深さの差が38($=2^1+2^2+2^5$)だったとする。 |
- | | + | |
- | | + | |
- | | + | |
+ | |||
+ | この時点で $a_t=b_t$ であれば、LCAは $a$ である。以下、それ以外の場合を考える。 | ||
== 同階層ながら互いに異なる、最も浅い祖先を求める == | == 同階層ながら互いに異なる、最も浅い祖先を求める == | ||
- | $a,b$ から1発で根にたどり着けるような最小の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。 | + | $a_t,b_t$ の深さは揃った。そこから1発で根を通り越さない最大の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。 |
- | * '' | + | * '' |
- | * '' | + | * '' |
* 同じなら何もしない | * 同じなら何もしない | ||
- | * '' | + | |
+ | | ||
+ | |||
+ | $k=0$ までやったら、$a_t, | ||
+ | |||
+ | |||
+ | ++++ 実装例(Python) | | ||
+ | |||
+ | * Verify: [[https:// | ||
+ | |||
+ | <sxh python> | ||
+ | class LcaDoubling: | ||
+ | """ | ||
+ | links[v] = { (u, w), (u, w), ... } (u: | ||
+ | というグラフ情報から、ダブリングによるLCAを構築。 | ||
+ | 任意の2頂点のLCAおよび距離を取得できるようにする | ||
+ | """ | ||
+ | |||
+ | def __init__(self, | ||
+ | self.depths = [-1] * n | ||
+ | self.distances = [-1] * n | ||
+ | prev_ancestors = self._init_dfs(n, | ||
+ | self.ancestors = [prev_ancestors] | ||
+ | max_depth = max(self.depths) | ||
+ | d = 1 | ||
+ | while d < max_depth: | ||
+ | next_ancestors = [prev_ancestors[p] for p in prev_ancestors] | ||
+ | self.ancestors.append(next_ancestors) | ||
+ | d <<= 1 | ||
+ | prev_ancestors = next_ancestors | ||
+ | |||
+ | def _init_dfs(self, | ||
+ | q = [(root, -1, 0, 0)] | ||
+ | direct_ancestors = [-1] * (n + 1) # 頂点数より1個長くし、存在しないことを-1で表す。末尾(-1)要素は常に-1 | ||
+ | while q: | ||
+ | v, p, dep, dist = q.pop() | ||
+ | direct_ancestors[v] = p | ||
+ | self.depths[v] = dep | ||
+ | self.distances[v] = dist | ||
+ | q.extend((u, | ||
+ | return direct_ancestors | ||
+ | |||
+ | def get_lca(self, | ||
+ | du, dv = self.depths[u], | ||
+ | if du > dv: | ||
+ | u, v = v, u | ||
+ | du, dv = dv, du | ||
+ | tu = u | ||
+ | tv = self.upstream(v, | ||
+ | if u == tv: | ||
+ | return u | ||
+ | for k in range(du.bit_length() - 1, -1, -1): | ||
+ | mu = self.ancestors[k][tu] | ||
+ | mv = self.ancestors[k][tv] | ||
+ | if mu != mv: | ||
+ | tu = mu | ||
+ | tv = mv | ||
+ | lca = self.ancestors[0][tu] | ||
+ | assert lca == self.ancestors[0][tv] | ||
+ | return lca | ||
+ | |||
+ | def get_distance(self, | ||
+ | lca = self.get_lca(u, | ||
+ | return self.distances[u] + self.distances[v] - 2 * self.distances[lca] | ||
+ | |||
+ | def upstream(self, | ||
+ | i = 0 | ||
+ | while k: | ||
+ | if k & 1: | ||
+ | v = self.ancestors[i][v] | ||
+ | k >>= 1 | ||
+ | i += 1 | ||
+ | return v | ||
+ | </ | ||
+ | ++++ | ||
+ | |||
+ | ===== ついでに求められる情報 ===== | ||
+ | |||
+ | ==== 2点間辺数、2点間距離 ==== | ||
+ | |||
+ | 頂点 $a,b$ を結ぶパスは、$c=lca(a, | ||
+ | |||
+ | 根から各頂点への距離 $dist[v]$ を記録しておけば、簡単な計算で2点間距離を求めることができる。 | ||
+ | |||
+ | $a,b$ の距離: $dist[a]+dist[b]-2dist[c]$ | ||
+ | |||
+ | 「$a$ から根まで遡上し、根から $b$ まで下る、という経路の内、根~$c$ の往復分が無駄である」と考えるとよい。 | ||
+ | |||
+ | | ||
+ | / | ||
+ | c e | ||
+ | / \ ... | ||
+ | | ||
+ | /\ | ||
+ | | ||
+ | |||
+ | ==== 2点間を結ぶパス中の1辺の最大(最小)コスト ==== | ||
+ | |||
+ | こちらは、もう少し面倒になる。 | ||
+ | |||
+ | max(min)には逆演算がないので、距離と同様に根から各頂点を結ぶパスの最大コストを記録してもダメ(その辺が根~$c$ に位置する場合、結局求めたい値はわからない)。 | ||
+ | |||
+ | LCAをダブリングで求める手法と同じようにすればよい。この場合、LCA自体を求めるアルゴリズムもダブリングの方がわかりやすい。 | ||
+ | |||
+ | * $maxp[k][v]$ | ||
+ | * $v$ から根に向かって $2^k$ 頂点を遡上するパスの中での最大コスト | ||
+ | |||
+ | $a~c$ 間の最大コストは、$a$ と $c$ の深さの差が例えば $d=2^1+2^2+2^5$ であれば、以下を求めればよい。 | ||
+ | |||
+ | * $\max(maxp[1][v], | ||
+ | * ただし、$v_p=v$ から $p$ 個遡上した頂点 | ||
+ | |||
+ | LCAもダブリングで実装していれば、これはLCAを求める過程で同時に求められる。 | ||
- | $k=0$ までやったら、$a,b$ の1つ親がLCM。 | + | $b$ からも同じことをして、その大きい方が、求める答えとなる。 |