6

このBFSのコードは、ウィキペディアの擬似コードを使用してC++で記述しました。この関数は2つのパラメーターs、tを取ります。sがソースノードでtがターゲットの場合、ターゲットがファウントの場合、検索はターゲット自体を返すか、そうでない場合は-1を返します。これが私のコードです：

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

struct vertex{
vector<int> edges;
bool visited;
};

int dist = 0;

int BFS(vertex Graph[],int v,int target){
deque<int> Q;
Q.push_front(v);
Graph[v].visited = true;
    while(!Q.empty()){
        int t = Q.back();
        Q.pop_back();
            if(t == target){
                return t;
            }
            for(unsigned int i = 0;i < Graph[t].edges.size();i++){
                int u = Graph[t].edges[i];
                if(!Graph[u].visited){
                    Graph[u].visited = true;
                    Q.push_front(u);
                }
            }
    }
    return -1;
} 

int main(){
int n;
cin >> n;
vertex Graph[n];
int k;
cin >> k;
for(int i = 0;i < k; i++){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    Graph[a].edges.push_back(b);
    Graph[b].edges.push_back(a);
}

for(int i = 0;i < n; i++){
    Graph[i].visited = false;
}

int s,t;
cin >> s >> t;

cout << BFS(Graph,s,t);

  }

私はウィキペディアでこれを読みました：

幅優先探索は、グラフ理論の多くの問題を解決するために使用できます。たとえば、次の
ようになります。2つのノードuとvの間の最短経路を見つける（経路の長さはエッジの数>>で測定）

関数BFSを変更して、最短パスをsからtに返し、パスが存在しない場合は-1を返すにはどうすればよいですか？

4

3 に答える 3

7

幅優先探索は、定義上、d開始点から離れた場所にあるすべてのノードにアクセスしてから、距離にあるノードにアクセスしますd+1。したがって、幅優先でグラフをトラバースすると、ターゲットノードに初めて遭遇したときに、可能な限り最短のルートでそこに到達します。

ネイサンS.」答えは正しいですが、この答えがなぜこれが機能するのかについてもう少し直感的になることを願っています。PaulDinhのコメントも正しいです。ネイサンの答えを変更して、実際のパスの代わりに距離を追跡することができます。

于 2012-11-01T04:54:28.823 に答える
4

新しいノードを生成するときは、ノードを生成した親のIDを追跡します。次に、目標に到達したら、開始状態に到達するまで親を逆方向にトレースします。たとえば、開始を独自の親としてマークできます。これは、開始状態であることを意味します。または、事前定義された値（-1）を使用して、親が存在しないことを示します。

したがって、コードでは、状態を訪問済みとしてマークする代わりに、親IDを使用します。親IDは、最初は-1に設定でき、変更されると更新されます。親IDは、親のグラフ構造内の場所だけにすることができます。

于 2012-11-01T04:50:08.110 に答える
-1

BFSアルゴリズムの適切な実装と説明については、この（CXXGraph）ライブラリのソースコードを確認してください。

于 2021-07-05T16:30:57.753 に答える