C++ の幅優先探索迷路
幅優先検索は、ツリーまたはグラフのデータ構造をトラバースまたは検索するためのアルゴリズムです。 各ノードで、アルゴリズムは親にアクセスする前に子にアクセスします。
つまり、親に上って子に移動するのではなく、各ツリー レベルの現在の位置から外側に展開します。
幅優先探索は、グラフの最短経路を見つけるために使用されます。 人工知能、コンピューター サイエンス、数学、社会科学など、多くの分野で解決策を見つけるために使用されています。
幅優先探索アルゴリズム
幅優先検索は、ツリーを幅優先で走査し、ノードを幅優先で展開する検索アルゴリズムです。
アルゴリズムは任意のノードから開始し、そのすべての子を展開します。 次に、それぞれの子に対して同じことを行います。以下同様です。
プロセスは、リーフ ノードに到達するか、ゴール状態を見つけると終了します。
あるノードから別のノードへの最短経路を見つけるには、そのノードからの距離を知る必要があります。 これは、グラフ内の任意の 2つのノード間のエッジの長さを加算することで計算できます。
C++ で幅優先探索迷路を実行する手順
C++ で幅優先探索迷路を実行する手順は次のとおりです。
-
グラフ オブジェクトを作成し、エッジと頂点で初期化します。
-
幅優先検索を実行する頂点を含むキューを作成します。
-
キューのフロント ポインタを
NULLとして初期化します。 -
幅優先検索を実行する頂点を含む空のリストを作成します。
-
リストのフロント ポインタを
NULLとして初期化します。 -
自分自身に接続されている開始頂点 (インデックス 0 の頂点) をキューに追加します。
-
開始頂点をリストに追加し、その親ポインタを
NULLに設定します。
キューが空でなくなると、そこから要素を取得し、未探索のノードに到達するまで幅優先探索アルゴリズムを再帰的に呼び出します。
最後に、キューが空になると、迷路の一端に到達し、その方向からの未探索のノードの検索を停止します。
C++ での幅優先探索迷路の例
これは、C++ の幅優先探索迷路の例です。 このコードは、アルゴリズムを実装して、特定の開始ノードからグラフ内の他のすべてのノードへの最短パスを見つけます。
#include <bits/stdc++.h>
using namespace std;
#define HORI 3
#define VERT 3
struct Point {
int a;
int b;
};
struct queueNode {
Point de;
int sam;
};
bool isValid(int hori, int vert) {
return (hori >= 0) && (hori < HORI) && (vert >= 0) && (vert < VERT);
}
int horiNum[] = {9, 7, 9, 2};
int vertNum[] = {3, 3, 4, 5};
int BFS(int lk[][VERT], Point ace, Point hello) {
if (!lk[ace.a][ace.b] || !lk[hello.a][hello.b]) return -1;
bool visited[HORI][VERT];
memset(visited, false, sizeof visited);
visited[ace.a][ace.b] = true;
queue<queueNode> e;
queueNode s = {ace, 0};
e.push(s);
while (!e.empty()) {
queueNode curr = e.front();
Point de = curr.de;
if (de.a == hello.a && de.b == hello.b) return curr.sam;
e.pop();
for (int i = 0; i < 4; i++) {
int hori = de.a + horiNum[i];
int vert = de.b + vertNum[i];
if (isValid(hori, vert) && lk[hori][vert] && !visited[hori][vert]) {
visited[hori][vert] = true;
queueNode Adjcell = {{hori, vert}, curr.sam + 1};
e.push(Adjcell);
}
}
}
return -1;
}
int main() {
int lk[HORI][VERT] = {{3, 9, 2}, {4, 5, 3}, {0, 3, 0}};
Point source = {0, 0};
Point hello = {1, 1};
int sam = BFS(lk, source, hello);
if (sam != 1)
cout << "Shortest Path:" << sam;
else
cout << "Failed!!!";
return 0;
}
ここをクリック 上記のコードの動作を確認します。
Muhammad Adil is a seasoned programmer and writer who has experience in various fields. He has been programming for over 5 years and have always loved the thrill of solving complex problems. He has skilled in PHP, Python, C++, Java, JavaScript, Ruby on Rails, AngularJS, ReactJS, HTML5 and CSS3. He enjoys putting his experience and knowledge into words.
Facebook