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() {
    @R_674_9421@e 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;
        @R_674_9421@e temp;
    }
    return value;
}
/*----------------------------------------------------*/
bool Queue::isEmpty() {
    return (front == @R_944_6633@
}
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并且无法让他工作.我怎样才能改善我实施的这种方式以这种方式行事？