始点と終点がある開いた迷路があります。迷路を解くための BFS と DFS 探索アルゴリズムを書きました。私の BFS は最短の解を見つけますが、私の DFS (下、左、上、右) は解としてジグザグを作成します。これは正しいです？DFS は開かれた迷路でどのように動作する必要がありますか?
編集: http://postimg.org/image/n049oua8n/ここに P から始まるパスがあります。エンドポイントは一番下にありますが、中間パスは私には間違っているように見えます =/ アルゴリズムが列をスキップしていると思います。右？中間セクションを完全に埋める必要がありますか？
はい、正解です。DFS はグラフを詳細に調べます (そして、最短パスは見つけられません)。訪問のソースが与えられるとs、DFS はその近隣の 1 つを訪問しu、次にその近隣の 1 つを詳細uに調べます。特定のノードのすべてのネイバーが訪問されると、親ノードの別のネイバーが訪問されます。
一方、BFS は、訪問のソースが与えられると、s最初にすべての近隣を訪問し、次に深化を開始します。
それは正しいように聞こえます: DFS は最初の方向 (下) に可能な限り迷路の奥深くまで進み、それ以上進むことができない場合、最後の交差点までバックトラックして左に移動し、次に再び下に移動します。
ピクセルの DFS または BFS を作成することによって空間を色で塗りつぶす「フラッド フィル」と呼ばれるペイント アルゴリズムがあります。その動作のアニメーションは、2 つのグラフ検索アルゴリズムの違いをグラフィカルに表現しています。
これは BFS で満たされた食べ物です。スペースをあらゆる方向に検索することがわかります。
これは DFS を使用したフラッド フィルです。最初に一方向にスペースを検索し、次にバックトラックして穴を埋めます。
