c – 寻找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 << " ";
}

找到正确的“城镇”并存储它们进行印刷.问题是,这确实打印了所有可能性而不仅仅是正确的方法.例如,如果前面提到它也找到“布达佩斯 – 伦敦”并打印出来.我知道问题在于我在路上排列了每个“城镇”但未找到如何检查其正确性的方法.

我不确定我怎么能找到唯一(最高的)方式.我最近发现了这个alghoritm并且无法让他工作.我怎样才能改善我实施的这种方式以这种方式行事？