Search with BFS

Question

I am trying to find the shortest path using BFS alghoritm. for example, I add points to the map

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

I defined the queue

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

and tried to implement 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 << " ";
}

find the right "cities" and save them for printing. The problem is that this prints ALL the features not only correctly. for example, if mentioned earlier, he also finds Budapest London and prints it. I know that the problem is that I put in each "city" in the way, but I can not find a way to verify its correctness.

I'm not quite sure how I can find ONLY (shorest) path. I recently found out about this algorithm and cannot make it work. How can I improve this algorithm that I implemented to behave this way?

Answer 1

, "", "" node. check .

, , if , .

, .

, BFS, . , node node , .

:

#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