用 BFS 找路

Question

我正在尝试使用 BFS 算法找到最短路径。例如我在地图上加了一个点

     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 << " ";
}

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

我不确定如何才能找到唯一（最接近）的方式。我最近发现了这个算法，但无法让他工作。我怎样才能改进我实现的这个算法以这样的方式运行？

Answer 1

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

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

最后只需要通过parents，就可以到达目的地了。

另请注意，我将 BFS 更改为从目的地开始。我这样做是因为否则从最后一个节点迭代回到第一个节点会 return 与您需要的路径相反。

代码如下：

#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;
}

这是输出。第一个是 w/o "london"->"moscow" 边，第二个是将该边添加到图中。

berlin london budapest moscow
berlin london moscow

用 BFS 找路

Finding way with BFS

c++

breadth-first-search

c++11