差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:graph_theory:lowest_common_ancestor [2019/12/04] – [ダブリング] 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 ==== |
===オイラーツアー=== | ===オイラーツアー=== | ||
行 45: | 行 44: | ||
5 | 5 | ||
- | この変換により、木の祖先・子孫関係をわかりやすい形(1次元配列)で持つことができるため、 | + | この変換により、木の祖先・子孫関係を1次元配列で持つことができるため、 |
- | 1次元配列で扱える様々なデータ構造を利用できる。BIT、セグメント木、など。 | + | 1次元配列で扱える様々なデータ構造を利用できる(BIT、セグメント木など) |
===オイラーツアーを用いたLCA=== | ===オイラーツアーを用いたLCA=== | ||
- | LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で各頂点が最初に現れた位置も記録していく。 | + | LCAを求めるには、オイラーツアーで通りかかった順番に頂点番号と深さを記録していく。 |
+ | また、その過程で各頂点が最初に現れた位置も記録していく。 | ||
+ | (実際には、最初に現れた位置でなく、最初~最後までのどこかの位置であればよいが、通常は最初に記録しておくのが一番やりやすい) | ||
* '' | * '' | ||
行 67: | 行 68: | ||
こうすると、頂点 a と b のLCAは、以下で求められる。 | こうすると、頂点 a と b のLCAは、以下で求められる。 | ||
- | * それぞれが '' | + | * それぞれが '' |
- | * $a_i \lt b_i$ と仮定する | + | * $p_a \lt p_b$ と仮定する |
- | * '' | + | * '' |
* そいつがLCAである(このような頂点はただ1つ存在する) | * そいつがLCAである(このような頂点はただ1つ存在する) | ||
頂点(a, b) = (5, 4) のLCAを求める | 頂点(a, b) = (5, 4) のLCAを求める | ||
- | → ai = 3, bi = 6 | + | → pa = 3, pb = 6 |
eular_tour[3: | eular_tour[3: | ||
- | この中で最小は (1, 1) なので、深さ1の頂点1がLCA | + | この中で最小は (1, 1) なので、深さ1の頂点「1」がLCA |
もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、'' | もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、'' | ||
行 85: | 行 86: | ||
* 平方分割 | * 平方分割 | ||
* セグメント木 | * セグメント木 | ||
- | * Sparce | + | * Sparse |
+ | 基本的に更新は不要なので、前処理 O(NlogN)、クエリ O(1) で処理できるSparse Tableが高速。 | ||
==== ダブリング ==== | ==== ダブリング ==== | ||
- | 各頂点から、1個先の親、2個先の親、4個先の親、8個先の親、...を記録していく。 | + | ダブリングは、 |
- | * '' | + | |
+ | * 前計算結果を利用すると、たとえば21個先は「1個先の4個先の16個先」とたかだか logN 回の遷移で求められる | ||
+ | |||
+ | というアルゴリズム。これをLCAを求めるのに適用する。 | ||
+ | |||
+ | 各頂点から、1個先の親、2個先の親、4個先の親、8個先の親、...を記録していく。(便宜的に根の親は根とする) | ||
+ | |||
+ | | ||
* 頂点 v から 2k 個先の親の頂点番号 u | * 頂点 v から 2k 個先の親の頂点番号 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 の方が深いとし、深さの差が38(2進数で 100110)だったとする。 | + | 作業用の変数として at,bt を用意し、at←depth[a]、bt←depth[b] |
- | 立っているbitだけ頂点を遡っていく。0-indexedで1,2,5桁目が' | + | bt の方が深いとし、深さの差が38($=2^1+2^2+2^5$)だったとする。 |
- | | + | |
- | | + | |
- | | + | |
- | 以降 | + | この時点で |
== 同階層ながら互いに異なる、最も浅い祖先を求める == | == 同階層ながら互いに異なる、最も浅い祖先を求める == | ||
- | $a,b$ から1発で根にたどり着けるような最小の k から、k を1ずつ減らしながら以下を繰り返し行う。 | + | $a_t,b_t$ の深さは揃った。そこから1発で根を通り越さない最大の k から、k を1ずつ減らしながら以下を繰り返し行う。 |
- | * '' | + | * '' |
- | * '' | + | * '' |
* 同じなら何もしない | * 同じなら何もしない | ||
- | * '' | + | |
+ | | ||
+ | |||
+ | k=0 までやったら、at,bt の1つ親がLCM。 | ||
+ | |||
+ | |||
+ | ++++ 実装例(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,b) として、a から c までは木を遡上し、c から b まで下ることとなる。 | ||
+ | |||
+ | 根から各頂点への距離 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 から根に向かって 2k 頂点を遡上するパスの中での最大コスト | ||
+ | |||
+ | a~c 間の最大コストは、a と c の深さの差が例えば d=21+22+25 であれば、以下を求めればよい。 | ||
+ | |||
+ | * max(maxp[1][v],maxp[2][v2],maxp[5][v6]) | ||
+ | * ただし、vp=v から p 個遡上した頂点 | ||
+ | |||
+ | LCAもダブリングで実装していれば、これはLCAを求める過程で同時に求められる。 | ||
- | $k=0$ までやったら、a,b の1つ親がLCM。 | + | $b$ からも同じことをして、その大きい方が、求める答えとなる。 |