c++ - 用 BFS 找路

我正在尝试使用 BFS 算法找到最短的方法。例如
我在 map 上添加了一个点

     add("berlin",london")
     add("budapest","london")
     add("london","glassgow")
     add("budapest","moscow")
     find("berlin",moscow") // should return berlin , london , budapest,moscow

我已经定义了一个队列

struct node {
    string info;
    node *next;
};
/*----------------------------------------------------*/
class Queue {
    private:
        node *front;
        node *rear;
    public:
        Queue();
        ~Queue();
        bool isEmpty();
        void enqueue(string );
        string dequeue();
        void display();
        bool find(string);
};
/*----------------------------------------------------*/
void Queue::display(){
    node *p = new node;
    p = front;
    if(front == NULL){
        cout<<"Nothing to Display" << endl;
    }else{
        while(p!=NULL){
            cout<<p->info << endl;
            p = p->next;
        }
    }
}
/*----------------------------------------------------*/
Queue::Queue() {
    front = NULL;
    rear = NULL;
}
/*----------------------------------------------------*/
Queue::~Queue() {
    delete front;
}
/*----------------------------------------------------*/
void Queue::enqueue(string data) {
    node *temp = new node();
    temp->info = data;
    temp->next = NULL;
    if(front == NULL){
        front = temp;
    }else{
        rear->next = temp;
    }
    rear = temp;
}
/*----------------------------------------------------*/
string Queue::dequeue() {
    node *temp = new node();
    string value;
    if(front == NULL){
        cout<<"Queue is Emtpty" << endl;
    }else{
        temp = front;
        value = temp->info;
        front = front->next;
        delete temp;
    }
    return value;
}
/*----------------------------------------------------*/
bool Queue::isEmpty() {
    return (front == NULL);
}
bool Queue::find( string name){
    node *temp = rear;
    while( temp != nullptr ){
        if( temp -> info == name){
            return true;
        }
        temp = temp -> next;
    }
    return false;
}

并尝试实现 bfs

class Graph {
    private:
        map< string , map<string, int >> graf;
    public:
        Graph(){};
        ~Graph(){};
        bool isConnected(string , string );
        void addEdge    (string one , string two);
        void BFS(string ,string);
};
/*----------------------------------------------------*/
bool Graph::isConnected(string one , string two){
    return (graf[one][two] == 1 || graf[two][one] == 1 );
}
/*----------------------------------------------------*/
void Graph::addEdge( string one , string two){
    graf [one][two] = graf[two][one] = 1;
}

/*----------------------------------------------------*/
void Graph::BFS(string s , string m){
    Queue one;
    map<string , bool> check;

    vector<string> path;
    for( auto &x : graf){
        check[x.first] = false;
    }

    check[s] = true;
    one.enqueue(s);
    path.push_back(s);

    string tmp = one.dequeue();
    for( auto &x: graf){
        if( isConnected(tmp , x.first)  && !check[x.first] ){
            one.enqueue(x.first);
            check[x.first] = true;
            path.push_back(x.first);
            if(x.first == m){
                break;
            }
        }
    }

    for( auto &x: path )
        cout << x << " ";
}

找到正确的“城镇”并将其存储以供打印。问题是，这确实打印了所有可能性，而不仅仅是正确的方式。例如，如果前面提到过，它还会找到“budapest - london”并打印出来。我知道问题在于我将每个“城镇”排入队列，但找不到如何检查其正确性的方法。

我不确定如何找到唯一的(海岸最远的)方式。我最近发现了这个算法并且无法让他工作。我该如何改进我实现的这种行为方式？

最佳答案

您可以保留每个节点的“父”，而不是将节点放在“路径”中。我已经更改了您的代码并使用 check 变量作为父数据结构。

如果未设置父项，则不会检查，因此 if 语句也会检查是否设置了父项。

最后只需要经过 parent ，就可以到达目的地。

另请注意，我将 BFS 更改为从目的地开始。我这样做是因为否则从最后一个节点返回到第一个节点将返回所需路径的反向。

这是代码:

#include <iostream>
#include <map>

using namespace std;

struct node {
    string info;
    node *next;
};
/*----------------------------------------------------*/
class Queue {
    private:
        node *front;
        node *rear;
    public:
        Queue();
        ~Queue();
        bool isEmpty();
        void enqueue(string );
        string dequeue();
        void display();
        bool find(string);
};
/*----------------------------------------------------*/
void Queue::display(){
    node *p = new node;
    p = front;
    if(front == NULL){
        cout<<"Nothing to Display" << endl;
    }else{
        while(p!=NULL){
            cout<<p->info << endl;
            p = p->next;
        }
    }
}
/*----------------------------------------------------*/
Queue::Queue() {
    front = NULL;
    rear = NULL;
}
/*----------------------------------------------------*/
Queue::~Queue() {
    delete front;
}
/*----------------------------------------------------*/
void Queue::enqueue(string data) {
    node *temp = new node();
    temp->info = data;
    temp->next = NULL;
    if(front == NULL){
        front = temp;
    }else{
        rear->next = temp;
    }
    rear = temp;
}
/*----------------------------------------------------*/
string Queue::dequeue() {
    node *temp = new node();
    string value;
    if(front == NULL){
        cout<<"Queue is Emtpty" << endl;
    }else{
        temp = front;
        value = temp->info;
        front = front->next;
        delete temp;
    }
    return value;
}
/*----------------------------------------------------*/
bool Queue::isEmpty() {
    return (front == NULL);
}
bool Queue::find( string name){
    node *temp = rear;
    while( temp != nullptr ){
        if( temp -> info == name){
            return true;
        }
        temp = temp -> next;
    }
    return false;
}

class Graph {
    private:
        map< string , map<string, int >> graf;
    public:
        Graph(){};
        ~Graph(){};
        bool isConnected(string , string );
        void addEdge    (string one , string two);
        void BFS(string ,string);
};
/*----------------------------------------------------*/
bool Graph::isConnected(string one , string two){
    return (graf[one][two] == 1 || graf[two][one] == 1 );
}
/*----------------------------------------------------*/
void Graph::addEdge( string one , string two){
    graf [one][two] = graf[two][one] = 1;
}

/*----------------------------------------------------*/
void Graph::BFS(string s , string m){
    Queue one;
    map<string , string> check;

    for( auto &x : graf){
        check[x.first] = "-";
    }

    check[m] = "";
    one.enqueue(m);

    while (!one.isEmpty())
    {
        string tmp = one.dequeue();
        if(tmp == s){
            string c = tmp;
            while (c != m) {
                cout << c << " ";
                c = check[c];
            }
            cout << c << endl;
            return;
        }
        for( auto &x: graf){
            if( isConnected(tmp , x.first)  && check[x.first] == "-" ){
                one.enqueue(x.first);
                check[x.first] = tmp;
            }
        }
    }

}

int main()
{
    Graph g;
    g.addEdge("berlin","london");
    g.addEdge("budapest","london");
    g.addEdge("london","glassgow");
    g.addEdge("budapest","moscow");
    g.BFS("berlin","moscow");
    g.addEdge("london", "moscow");
    g.BFS("berlin","moscow");
    return 0;
}

这是输出。第一个是没有“伦敦”->“莫斯科”边，第二个是将该边添加到图形中。

berlin london budapest moscow
berlin london moscow

关于c++ - 用 BFS 找路，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37133548/