Breadth First Search question C++

This is my first time programming C++ and I've been asked to code a breadth first search where given this class

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 removeConnec开发者_Python百科t();
  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 is a struct consisting of string name and int players. Could someone explain to me how I'd go about making the BFS?

Thanks in advance!

EDIT:

I understand the algorithm for BFS, but since I've only ever programmed C, understanding OO programming is quite confusing to me, given that interface, where do I start with this BFS, do I make a new function which makes the BFS comparing, the start string with the 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;
}

---

Breadth First search is all about asking 2 questions

1. What state am I at right now?
2. What states can I get to from here?

The idea is to have an initial state and continuously ask yourself these 2 questions until

1. No more states left.
2. I have reached the destination state.

BFS usually uses a Queue to which you simply add any new states you find and simply pop from the front of the queue whenever you want to process a new state and add any new states to the end of the queue.

---

The route class is only a mechanism to store the routes that you find using BFS. At least that's how I'm interpreting it. The BFS algorithm will be a stand alone function that will call methods of the route class at appropiate times. Since a BFS needs to maintain information about multiple routes it will have to create multiple route objects in some sort of list or queue. Each step of the BFS will take one route object from the queue, copy it and call addConnect on it to move to the next location, then place it back on the queue. Repeat until you get to your destination, then return the route object representing the shortest path from your BFS function.

Something like that anyway.