幅優先探索
見つかったノードを全て記録する必要があるので、幅優先探索の空間計算量はO(|V|)となる。ここで|V|はグラフ内のノードの数である。または、 O ( B M ) {\displaystyle O(B^{M})} ということができる。Bは枝分かれの最大数で、Mは木の最長経路の長さ。指数関数故に、幅優先探索は大量の情報から探索する事に向かない根拠になる。