幅優先探索の質問C++

Question

これが私の初めてのプログラミングC++であると私は

class route { 

    friend ostream& operator<<(ostream& os, const route& p); 

public: 

    route(const string& startPlayer); 
    int getLength() const { return links.size(); }; 
    void addConnect(const sport& s, const string& player); 
    void removeConnect(); 
    const string& getLastPlayer() const; 

private: 

    struct Connect { 
    sport s; 
    string player; 
    Connect() {} 
    Connect(const sport& s, const string& player) : s(s), player(player) {} 
    }; 

    string startPlayer; 
    vector<Connect> links; 
}; 

sportこのクラス与えられた幅優先探索をコーディングするように求めてきたstring nameとint playersからなる構造体です。誰かが私にBFSの作り方を説明することができましたか？

ありがとうございます！

編集：私はBFSのアルゴリズムを理解し、私は唯一のこれまでCをプログラムしてきたことから、理解オブジェクト指向プログラミングは、私はこのBFSで始まるかそのインターフェイス、与えられた、私にはかなり混乱して

、Iを行いますBFSは比較になり新しい関数を作る、target string

namespace { 

string promptForSPlayer(const string& prompt, const spdb& db) 
{ 
    string response; 
    while (true) { 
    cout << prompt << " [or <enter> to quit]: "; 
    getline(cin, response); 
    if (response == "") return ""; 
    vector<sport> splist; 
    if (db.getsplist(response, splist)) return response; 
    cout << "It's not here: \"" << response << "\" in the sports database. " 
    << "Please try again." << endl; 
    } 
} 

} 

int main(int argc, char *argv[]) 
{ 
    if (argc != 2) { 
    cerr << "Usage: sports" << endl; 
    return 1; 
    } 

    spdb db(argv[1]); 

    if (!db.good()) { 
    cout << "Failed to properly initialize the spdb database." << endl; 
    cout << "Please check to make sure the start files exist and that you have permission to read them." << endl; 
    exit(1); 
    } 

    while (true) { 
    string start = promptForSplayer("Player", db); 
    if (start == "") break; 
    string target = promptForSplayer("Another Player", db); 
    if (target == "") break; 
    if (start == target) { 
     cout << "Good one. This is only interesting if you specify two different people." << endl; 
    } else { 
     // replace the following line by a call to your generateShortestPath routine... 
     cout << endl << "No path between those two people could be found." << endl << endl; 
    } 
    } 
    return 0; 
} 

Answer 1

幅優先探索とstart stringはすべて2つの質問をする程度である

1. 私は今どのような状態ですか？
2. ここからどのような状態になることができますか？

アイデアは、初期状態を持っており、継続的にこれ以上の状態が残っていない

1. まで自分自身にこれらの2つの質問を依頼することです。
2. 私は行き先の状態に達しました。

BFSは通常、あなたは、単にあなたが見つけると、単にあなたが新しい状態を処理し、キューの最後に、新しい状態を追加したい時はいつでもキューの先頭からポップ、新しい状態を追加したキューを使用しています。

Answer 2

ルートクラスは、BFSを使用して見つかったルートを格納するメカニズムにすぎません。少なくとも私はそれをどのように解釈しているのですか。 BFSアルゴリズムは、適切な時間にルートクラスのメソッドを呼び出すスタンドアローン関数になります。 BFSは複数のルートに関する情報を維持する必要があるため、何らかの並べ替えのリストまたはキューで複数のルートオブジェクトを作成する必要があります。 BFSの各ステップは、キューから1つのルートオブジェクトを取り出し、コピーしてaddConnectを呼び出して次の場所に移動し、キューに戻します。目的地に到着するまで繰り返す。その後、BFS機能からの最短経路を表す経路オブジェクトを返す。

とにかくそういうものです。