广度优先搜索问题 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呢？我是否需要创建一个新函数，将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;
}

- FHr

---

这里的伪代码非常清晰地展示了广度优先搜索算法：http://en.wikipedia.org/wiki/Breadth-first_search - RageD

我还没有尝试过任何事情，因为我不知道如何开始。 - FHr

对C++编程感到困惑吗？ - Brett Walker

你具体是对什么感到困惑？“面向对象编程”是一个广泛的主题。 - BlackJack

是的，我需要调用连接结构体，检查玩家是否与用户输入的玩家匹配，并按照这种方式继续算法吗？ - FHr

Answer 1

广度优先搜索的核心思想就是回答两个问题：

1. 当前状态是什么？ 2. 从当前状态可以到达哪些状态？

通过一个初始状态，不断地询问这两个问题，直到以下情况之一出现：

1. 没有更多的状态可以处理了。 2. 到达了目标状态。

BFS通常使用队列来存储新发现的状态，只需将其添加到队列的末尾，并在需要处理新状态时从队列的前面弹出，并将任何新状态添加到队列的末尾。

- Jesus Ramos

---

广度优先搜索和深度优先搜索几乎是完全相同的算法。一个使用后进先出（LIFO）栈，另一个使用先进先出（FIFO）队列。除此之外，它们完全一样。 - Ben Voigt

Answer 2

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

大概就是这样。

- john