以下の内容はhttps://blog.hamayanhamayan.com/entry/2017/04/10/163548より取得しました。
- 木をDFSしたときの順番で頂点を記録する手法
- pre-order : 頂点に到着したら記録
- post-order : 頂点から離れるときに記録
- 用途
- 根付き木のある頂点からの部分木に対するクエリを処理
- ある頂点がある頂点の部分木に含まれるかを高速に判定する
- 上手くオイラーツアーを作るとパスのコストの総和が取れる
- 木をBFSしたときの順番で頂点を記録するBFS Euler Tourというのもある
- オイラーツアーのbfs-order
- 用途としては、ある頂点から一定の距離にある頂点に対して区間操作を行える
問題
- DFS Euler Tour
- BFS Euler Tour
オイラーツアーっぽくやる問題
- 頂点に入ったら操作をして、出るときに逆操作をする系の問題
以上の内容はhttps://blog.hamayanhamayan.com/entry/2017/04/10/163548より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14
