广度优先搜索问题C++

这是我第一次编程C++，我一直在问哪里给这个类广度优先搜索问题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，我做使一个新的功能，这使得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; 
}

来源

2011-08-09 FHr

该算法在伪代码中的布局非常好：http://en.wikipedia.org/wiki/Breadth-first_search – RageD

我还没有尝试过任何东西，因为我很困惑，因为如何开始 – FHr

编程困惑在C++中？ –

广度优先搜索是所有关于询问2个问题

我现在在哪个状态？
我可以从这里得到什么状态？

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

没有更多的国家离开。
我已到达目的地州。

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

来源

2011-08-09 02:39:04

宽度优先和深度优先几乎完全相同的算法。一个使用LIFO堆栈，另一个使用FIFO队列。除此之外，它们是相同的。 –

我意识到这一点。 –

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

反正就是这样。

来源

2011-08-09 05:20:03 john

广度优先搜索问题C++

回答

相关问题