Tarjanのオフライン最小共通祖先アルゴリズム

コンピュータサイエンスにおいて、Tarjan のオフライン最低共通祖先アルゴリズムは、和集合データ構造に基づいて、ツリー内のノードのペアについて最低共通祖先を計算するアルゴリズムです。根付きツリーT内の 2 つのノードdとeの最低共通祖先は、 dとeの両方の祖先であり、 T内で最も深いノードgです。この手法は、 1979 年にこの手法を発見したRobert Tarjanにちなんで名付けられました。Tarjan のアルゴリズムはオフライン アルゴリズムです。つまり、他の最低共通祖先アルゴリズムとは異なり、最低共通祖先を求めるすべてのノード ペアを事前に指定する必要があります。このアルゴリズムの最も単純なバージョンでは、和集合データ構造を使用します。このデータ構造は、他の最低共通祖先データ構造とは異なり、ノード ペアの数とノード数の大きさが同程度である場合、1 回の操作あたり定数時間以上かかることがあります。その後、Gabow と Tarjan (1983)によって改良され、このアルゴリズムは線形時間まで高速化されました。

擬似コード

以下の擬似コードは、ノードnの子ノードがn.children集合に含まれるツリーのルートrを与えられた場合に、 P内の各ペアの最下位共通祖先を決定します。このオフラインアルゴリズムでは、集合Pを事前に指定する必要があります。これは、分離集合データ構造のMakeSet、Find、およびUnion関数を使用します。MakeSet (u) はu を単一集合に削除し、 Find(u) はuを含む集合の標準代表を返し、Union(u,v) はuを含む集合とvを含む集合を結合します。TarjanOLCA( r ) は最初にルートrに対して呼び出されます。 

関数TarjanOLCA(u)は メイクセット(u) u.祖先 := u u.childrenの各vに対して タージャンOLCA(v) ユニオン(u, v) Find(u).ancestor := u u.color := 黒 P内の{u, v}となる各vに対して、 v.color == blackならば 「タージャンの最下位共通祖先」を印刷 + u + 「そして」 + v + 「は」 + Find(v).ancestor + 「です。」

各ノードは最初は白ですが、そのノードとそのすべての子ノードが訪問された後に黒に変わります。

調査対象となる 各ノードペア{u,v}について:

  • vがすでに黒の場合(つまり、ツリーの後順トラバーサルでv がu の前に来る場合): u が黒に着色された後、このペアの最低共通祖先はFind(v).ancestorとして利用できますが、 uとvの LCA が黒に着色されていない間のみです。
  • それ以外の場合: vが黒くなると、 LCA は黒くならない間はFind(u).ancestorとして利用できるようになります。

Tarjan (1979)によれば、時間計算量は O((m + n)a(m + n, n)) である。ここで、m は辺の数、n は頂点の数、a は逆アッカーマン関数である。ただし、u に対応する頂点ペアを見つけるのにかかる時間は頂点ごとに定数時間である。この論文では、隣接リスト（論文では隣接構造と呼んでいる） の使用が推奨されている。

参考までに、分離セットフォレスト用のMakeSet、Find、Unionの最適化されたバージョンを次に示します。 

関数MakeSet(x)は x.親:= x x.rank := 1 関数Union(x, y)は xRoot := Find(x) yRoot := Find(y) xRoot.rank > yRoot.rankの場合 yRoot.parent := xRoot そうでない場合、 xRoot.rank < yRoot.rankの場合 xRoot.parent := yRoot そうでない場合、 xRoot.rank == yRoot.rankの場合 yRoot.parent := xRoot xRoot.rank := xRoot.rank + 1 関数Find(x)は x.parent != xの場合 x.parent := Find(x.parent) x.parent を返す

アルゴリズムの高速化

入力 LCA クエリを前処理して、アルゴリズムの動作を 1 桁高速化することが可能になります。 

関数Preprocess(P)は m := 空のマップ P内の各{u, v}に対して、 uがmにマッピングされていない場合は m[u] := ∅ m[u] := m[u] ∪ {(u, v)} vがmにマッピングされていない場合 m[v] := ∅ m[v] := m[v] ∪ {(u, v)} m を返す
関数GetOpposite(q, u)は q[0] == uの場合q [1] を返し、 q[0] を返す。
関数FasterTarjanOLCA(u)は メイクセット(u) u.祖先 := u u.childrenの各vに対して より速いTarjanOLCA(v) ユニオン(u, v) Find(u).ancestor := u u.color := 黒 m[u] == nilの場合、 m[u]内の各qに対してdoを返す v := GetOpposite(q, u) v != nil かつv.color == black の場合、 「" + u + " と " + v + " の LCA は " + Find(v).ancestor + " です。」 と出力します。

最適化の考え方は、ノードを入力クエリのリスト内の対応するノードに関連付けることです。

参考文献

「 https://en.wikipedia.org/w/index.php?title=Tarjan%27s_off-line_lowest_common_ancestors_algorithm&oldid=1302316249」より取得