内容へ移動

現在位置: トップページ » アルゴリズム » graph_theory » 最小共通祖先

文書の表示

管理サイトマップ

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

--- programming_algorithm:graph_theory:lowest_common_ancestor [2019/12/26] – [ダブリング] ikatakos
+++ programming_algorithm:graph_theory:lowest_common_ancestor [2020/02/06] – [ダブリング] ikatakos
@@ 行 127: / 行 127: @@
 $k=0$ までやったら、$a,b$ の1つ親がLCM。
+++++ 実装例(Python) |
+<sxh python>
+class LcaDoubling:
+    """
+    links[v] = { (u, w), (u, w), ... }  (u:隣接頂点, w:辺の重み)
+    というグラフ情報から、ダブリングによるLCAを構築。
+    任意の2頂点のLCAおよび距離を取得できるようにする
+    """
+    depths: list
+    distances: list
+    ancestors: list
+    def __init__(self, n, links, root=0):
+        self.depths = [-1] * n
+        self.distances = [-1] * n
+        prev_ancestors = self._init_dfs(n, links, root)
+        self.ancestors = [prev_ancestors]
+        max_depth = max(self.depths)
+        d = 1
+        while d < max_depth:
+            next_ancestors = [prev_ancestors[prev_ancestors[v]] for v in range(n)]
+            self.ancestors.append(next_ancestors)
+            d <<= 1
+            prev_ancestors = next_ancestors
+    def _init_dfs(self, n, links, root):
+        q = [(root, -1, 0, 0)]
+        direct_ancestors = [0] * n
+        while q:
+            v, p, dep, dist = q.pop()
+            direct_ancestors[v] = p
+            self.depths[v] = dep
+            self.distances[v] = dist
+            q.extend((u, v, dep + 1, dist + w) for u, w in links[v] if u != p)
+        return direct_ancestors
+    def lca(self, u, v):
+        du, dv = self.depths[u], self.depths[v]
+        if du > dv:
+            u, v = v, u
+            du, dv = dv, du
+        tu = u
+        tv = self.upstream(v, dv - du)
+        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, u, v):
+        lca = self.lca(u, v)
+        return self.distances[u] + self.distances[v] - 2 * self.distances[lca]
+    def upstream(self, v, k):
+        i = 0
+        while k:
+            if k & 1:
+                v = self.ancestors[i][v]
+            k >>= 1
+            i += 1
+        return v
+</sxh>
+++++
 ===== バリエーション =====

文書の表示

メディアマネージャー文書の先頭へ

CC Attribution 4.0 International