深さ制限探索
通常の深さ優先探索のように、深さ制限探索も一様な探索を行う。深さ優先探索と異なるのは、探索する深さを制限する点である。制限を越えて探索木を深くしていくことがないため、無限の経路に捉われたり、環状の経路に捉われたりすることがない。従って、深さ制限探索は制限された深さの範囲内で、あらゆるグラフの最適解を求めることができる。
深さ制限探索は深さ優先探索の一種であるため、時間計算量は通常の深さ優先探索と同じで O( | V | + | E | {\displaystyle \vert V\vert +\vert E\vert } ) である。ここで、 | V | {\displaystyle \vert V\vert } は探索するグラフの頂点数、 | E | {\displaystyle \vert E\vert } は枝の数である。ただし、深さ制限探索はグラフ全体を探索するのではなく、制限された範囲内だけを探索する。
深さ制限探索は深さ優先探索の一種であるため、空間計算量は通常の深さ優先探索と同じである。