广度优先搜索问题 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 组成的结构玩家。有人可以向我解释一下如何制作 BFS 吗？

提前致谢！

编辑：

我了解 BFS 的算法，但由于我只编写过 C 语言，因此理解 OO 编程对我来说非常困惑，考虑到该接口，我从哪里开始使用这个 BFS，我是否创建一个新函数来使 BFS将起始字符串与目标字符串进行比较

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

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

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

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

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

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

Answer 2

路由类只是一种存储使用 BFS 找到的路由的机制。至少我是这么解释的。 BFS 算法将是一个独立的函数，它将在适当的时间调用路由类的方法。由于 BFS 需要维护有关多个路由的信息，因此它必须在某种列表或队列中创建多个路由对象。 BFS 的每一步都会从队列中取出一个路由对象，复制它并对其调用 addConnect 以移动到下一个位置，然后将其放回队列中。重复此操作，直到到达目的地，然后从 BFS 函数返回表示最短路径的路由对象。

无论如何，类似的事情。