データ構造とアルゴリズム

DFS深さ優先探索C ++実装（迷路問題）



Dfs Depth First Search C Implementation



実装コード

#include using namespace std const int MAXSIZE = 100 int maze[MAXSIZE][MAXSIZE] vector< pair<int, int> > path//The dynamic array path is used to store the path bool flag = true//Used for recursive end return int dir[4][2] = {//Direction array {- 1, 0}, {1, 0}, {0, - 1}, {0, 1} } void DFS(int y, int x){ if(!flag) return if(maze[y][x] == 3){ path.push_back(make_pair(y,x)) flag = false return } if(maze[y][x] == 1) return //The above judgment statement detects whether it reaches the end of the recursion maze[y][x] = 1//Mark has been visited path.push_back(make_pair(y,x))//Add this vertex to the path for(int i = 0 i < 4 && flag i++){//Continue recursive search in four directions DFS(y + dir[i][0], x + dir[i][1]) } if(flag) path.pop_back()//Exit the path if this vertex is not found } int main(int argc, char const *argv[]) { int n, m int x, y if(argc == 1) { argv[1] = 'text.txt' } freopen(argv[1],'r', stdin) while(~scanf('%d%d', &n, &m)){ for(int i = 0 i <= n + 1 i++) maze[0][i] = maze[m + 1][i] = 1 for(int i = 0 i <= m + 1 i++) maze[i][0] = maze[i][n + 1] = 1 for(int i = 1 i <= m i++) for(int j = 1 j <= n j++){ scanf('%d', &maze[i][j]) if(maze[i][j] == 2){ x = j y = i } }//Enter data and set the end point path.push_back(make_pair(y,x)) for(int i = 0 i < 4 i++){ DFS(y + dir[i][0], x + dir[i][1])//Search in four directions recursively } //Print the result printf('Steps: %d ',path.size()) printf('Path: ') for(int i = 0 i < path.size() i++) printf('%d %d ', path[i].first, path[i].second) } return 0 }

アルゴリズムのアイデア

このアルゴリズムは、隣接行列、隣接テーブル、その他のデータ構造を使用せず、迷路を歩くアルゴリズムを実装するだけです。下付き文字yとxを変更するには、方向配列dirを設定します。深さ優先探索は、開始点から開始し、訪問した頂点をたどります。の最初の隣接ポイントを再帰的に検索し、「深い」ポイントにアクセスし（隣接ポイントにアクセス済み）、前のポイントに戻って2番目の頂点にアクセスし、以下同様に、探しているノードにアクセスするまで続けます。すべての頂点にアクセスして終了します。

テストデータ

6 6 2 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 3 0 0 0 0 1

試験結果

テスト結果によって出力されるパスは、迷路配列の添え字です

Steps: 14 Path: 1 1 1 2 1 3 1 4 1 5 2 5 3 5 4 5 5 5 6 5 6 4 6 3 6 2 6 1

やっと

このアルゴリズムは、DFSアルゴリズムに基づいて、迷路の問題を解決するために使用されます 、4つの方向はそれ自身の仮定です。グラフ走査アルゴリズムには同様の方向はありません。ノードの隣接ポイントのみを検索し、隣接ポイントの最大数は0より大きい任意の値にすることができます。グラフが大きすぎる場合は、再帰の代わりにスタックを使用するか、BFSアルゴリズムを使用できます。 BFSアルゴリズムとDFSアルゴリズムはどちらも、グラフ全体をトラバースするだけです。 各頂点は一度だけ （完全なグラフトラバーサルの場合）、時間の複雑さはO（n）であるため、nはグラフの頂点の数ですが、DFSアルゴリズムの再帰的メソッドを使用した多数の再帰的関数呼び出しにより、ユーザープログラムは次のようになります。再帰スタックをオーバーフローさせる時間が長すぎるエラーや実行時エラーを引き起こすには、再帰の代わりにプログラムでスタックを開くか（すべての再帰セックスは、スタックで非再帰的な方法として実装できます）、またはキューベースのBFSアルゴリズムを使用します。多数の再帰呼び出しを回避するため。ローカル変数を初期化し、メモリおよびその他の時間とスペースのオーバーヘッドを割り当てます。

ブロガーのレベルが限られているため、避けられない省略があります。読者は、不必要な誤解を避けるために、いつでも批判して訂正することを歓迎します！