幅優先探索– tag –
-
コンピュータ科学 深掘り
二分探索木と3つの巡回 — 木にしたのに一直線になる
二分探索木は「探索が O(log n) になるデータ構造」だと覚えていました。実際に 1,2,3,... を順に入れてみたら、木の高さが 39999 になり、1件探すのに平均 20000 回比較していました。木ではなく、右に伸びた連結リストになっていたのです。この記事では VM の中に ~/cslab/tree を作り、insert / search / min / max / delete を自分で書き、削除の3パターンを図で確かめます。3つの巡回を並べて in-order だけがソート済みで出てくることを見て、幅優先はキューで書きます。最後に並んだデータを入れて高さと探索時間を実測し、再帰版の巡回を 20000 件で落として、明示的なスタックのループ版に書き換えて全部消します。 -
コンピュータ科学 深掘り
グラフとBFS・DFS — 循環参照で探索が止まらない
グラフ理論は数学の話ではなく、npm の依存関係も Git の履歴も Docker Compose の depends_on も全部グラフです。木と違って輪ができるので、訪問済みを管理しないと探索が止まりません。隣接リストと隣接行列を両方書いてメモリを実測し、BFS と DFS を書いて訪問順と経路の長さを並べて見ます。輪のあるグラフで visited を外すと本当に止まらないことを、回数の上限を付けて安全に再現します。最後に循環検出・トポロジカルソート・連結成分・全域木まで、実際に動くコードで確かめます。
1