グラフアルゴリズムの基礎を学ぶーBFSとDFS

この記事は、グラフアルゴリズムシリーズの2番目の記事です。 概念と表現方法 BFSとDFS→現在地 UnionFind 最小全域木 単一始点最短経路問題 全点対最短経路問題（WIP） メンタルモデル 今回はグラフのデータの探索方法について紹介します。探索方法は概ね2つに分けられます。 幅優先探索（BFS: Breadth-First Search）、探索のレベルとの概念を用いて、ノードに隣接する全てのノードを優先的に探索するアルゴリズムです。 BFSメンタルモデル（出典） 深さ優先探索（DFS: Depth-First Search）、幅優先と違い、ノードの隣接ノードのどれか1つを選択して、隣接ノードがなくなるまで繰り返して探索するアルゴリズムです。 DFSメンタルモデル（出典） ここで理解のためにまずは二分木の探索から見てみましょう。 二分木の探索 二分木のDFS探索には、pre-ord