c++ - 广度优先搜索题 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 语言，理解 OO 编程对我来说非常困惑，考虑到该接口(interface)，我从哪里开始这个 BFS，我是否创建一个新函数使BFS比较，start string与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

广度优先搜索就是问 2 个问题

1. 我现在处于什么状态？
2. 我可以从这里到达哪些州？

想法是有一个初始状态，不断问自己这2个问题，直到

1. 没有更多的状态了。
2. 我已经到达目的地状态。

BFS 通常使用一个队列，您只需将找到的任何新状态添加到其中，只要您想要处理一个新状态，只需从队列的前面弹出，并将任何新状态添加到队列的末尾即可。