木構造
解の形を木構造に限定して考える
- 木には良い性質が多いので、グラフなどの問題で、解の形を「木」に限定して探索する、など
- 最適解が木構造になる、または、最適スコアに近いものが得られる場合でないと、形を限定するのは普通はあまり良くない
- AHC036
分解
- 木分解
- 重心分解
- Heavy-Light Decomposition
部分変更
- 木に1辺を追加するとサイクルになるので、サイクル上の別の1辺を削除すると別の木が得られる
グリッドで木構造を考える
DFS木、BFS木
- 各頂点に1回だけ訪問するようにグラフを深さ優先探索順か、幅優先探索順かで辿ったときに使った辺でできる木
- 巡回方法(2分木の場合)
- 行きがけ順(pre-order)
- 通りがけ順(in-order)
- 帰りがけ順(post-order)
- レベル順(level-order)
全域木
最短経路木(Shortest-path tree)
- ある頂点から他の頂点までの移動コストが最小になるような木
- 辺のコストがある場合はダイクストラ、コストなければBFS、などで構築
- 全域木
- グラフの構造が変化する場合(頂点や辺の追加削除など)、最短経路木の該当の部分のみ修正し、その部分木のみを更新すれば、高速に更新できる
最小シュタイナー木
オイラーツアーテクニック
- 木の辺を2つの有向辺とみなしてオイラー閉路をDFSで作り、通過した辺を順番に配列にメモる
- 部分木が、メモした配列の連続区間に対応する
- ビームサーチで、状態遷移の過程をオイラーツアーの木で持って処理するなどにも使える