深さ優先探索と幅優先探索、再帰表現・非再帰表現との親和性

深さ優先探索は再帰表現がしやすく、幅優先探索は非再帰表現がしやすいと言う。その理由は次のようになる。

深さ優先探索では、探索過程において、多段階の保留状態を生み、その多段階の保留状態は、『当該段階』『当該段階より１つ上の段階』『当該段階より１つ下の段階』の３段階で構成され、この『３段階構成』は、多段階のそれぞれの段階で発生するものであるから、この『３段階構成』を多段階に発生させる部分を『再帰表現』すると、探索構造全体が「上下の『３段階構成』と『上下の数列』の２規則」で表現しきれるからである。

他方、幅優先探索では、探索過程において、『３段階構成』を生むが、その構成要素を増やすことで網羅的探索に対応している。探索構造は、「上下の『３段階構成』」のみになっているわけである。ただし、深さ優先探索が２構造規則で表現されていたのに対して、幅優先探索で１構造規則になっているのには、理由があり、それは、『３段階構成』を利用した幅優先探索においては、探索を進める順序に、「古いものから先に処理する」という別の規則を定めているからである。

深さ優先探索でも『再帰表現』をしないのであれば、処理順規則という形の別規則を持ち込む必要があるだろう。

処理順規則は、キュー・スタックに任せるのが便利だろうが、それは各論に過ぎるので、こちらで。