Rubyで全探索（深さ優先探索、幅優先探索）を実装してみた - Qiita

はじめに アルゴリズム、というか競技プログラミングに関するネタです。 昨日までの自分にとって有益な情報なので、Qiitaに載せておきます。 これまで再帰を使った深さ優先探索しか理解できておらず、しかも理解が甘くて使おうとしても毎度ワタワタする始末。これではいかんと思い、以下3つのパターンについて極力シンプルな形で実装してみました。 深さ優先探索（DFS, Depth-First Search） 再帰による実装 スタックによる実装 幅優先探索（BFS, Breadth-First Search） キューによる実装 すべてRubyでの実装です。Ruby 2.3.3での動作を確認しています。 お題 アルファベット A, B, C からなる、3文字以下の文字列の組み合わせをすべて取得する。 このお題を、全探索で解きます。この手の全探索だと"迷路を解く"問題が定番ですが、シンプルさを重視した結果こん

[youko03]

"実質的に違っているのはスタックかキューかという部分だけ、つまり積んだものを末尾から取り出すか先頭から取り出すかの違いでしかありません" [ruby][アルゴリズム][DFS][BFS]