推移閉包

概要

各始点探索またはWarshallの段階不変条件により全頂点対の到達関係を計算する。

考え方

到達可能性を真偽値の行列で持ち、途中に許す頂点を一つずつ増やす。R[i][j]をR[i][j]∨(R[i][k]∧R[k][j])で更新すると、中継点集合に対する帰納法で全到達関係が得られる。

長さ0を含む到達関係なら対角をtrue、直接辺もtrue、他falseで初期化する。k=0,…,V−1を最外ループにして全i,jを更新する。k直前のRは中継に0,…,k−1だけを許すwalkであり、kを使わない場合と、i→k・k→jへ分ける場合のORで次段を得る。真偽値は一度trueになると戻らず、in-placeでも同じ閉包が得られる。

初回成立段階を欲しい場合は、初期のtrueを段階0とし、更新で初めてfalse→trueになった組へk+1を記録する。これは中継許可集合の段階であり、最短辺数ではない。bitset実装はR[i][k]がtrueの行iへR[k]をORする。正長cycleを判定したい場合は初期対角をtrueにせず、正長到達の定義を保持する。

成立条件と計算量

通常O(V³)時間・O(V²)空間。bitsetで行を合併すればword幅wのモデルでO(V³/w)程度。自分自身への長さ0の到達と正長のcycle到達を分ける。DAGで逆順に到達集合を合併する方法も使える。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。到達関係の推移性を行列更新やbitsetでまとめて計算する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 状態グラフ探索・到達関係。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-transitive-closure

推移閉包

習得する技能

  • 各始点探索または中継許可集合の段階不変条件を保つWarshall更新で推移閉包を求め、必要なら初回到達段階も記録できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

各始点探索またはWarshallの段階不変条件により全頂点対の到達関係を計算する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • 推移閉包の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠