How to get the path between 2 nodes using Breadth-First Search?

I am t开发者_开发问答rying to find a path between two nodes in a graph, where the edges are unweighted.

I am using a Breadth First Search, which stops when it finds the target, in order to find the existence of a path, but I am not sure how to get the path itself.

I tried looking at the list of visited nodes, but this did not seem to help. I saw someone answer this question using prolog, but I am a C++ programmer.

I also looked at Dijkstras algorithm, but this seems like over kill, since a simple Breadth-first Search has got me almost the whole way.

How to get the path between 2 nodes using Breadth-First Search?

In your node struct, you add a variable called parentNode which is the parent of that node in the path. In the end, you can retrieve the path by traversing from the goal node backward.

I found this simple algorithm which stores the path to the node along with the node in the queue here: https://stackoverflow.com/a/50575971/5883177 So when we pop a node from the queue, we also get the path to that node readily.

The code in the link is in python which uses tuples to store the pair. Here is a C++ implementation of the same which uses std::pair.

bool findPath(Node *n1, Node *n2, vector<Node*> &path)
{
    // We use queue to perform a BFS traversal and in addition to storing the
    // node we'll also store the path so far to the node.
    queue<pair<Node*,vector<Node*>>> q;
    
    // Visit the first node and add it to the queue.
    n1->visited=1;
    // Form the path, create a pair and add it the queue.
    vector<Node*> p;
    p.push_back(n1);
    q.push(make_pair(n1,p));
    
    while(!q.empty())
    {
        pair<Node*,vector<Node*>> curPair = q.front();
        q.pop();
        
        // visit all the unvisited nodes and check if there is n2 in it.
        for(Node *u : curPair.first->adjNodes ){
            if(u->visited == 0){
                
                if(u->value == n2->value){
                    // found our destination. Return true
                    // form the path by appending this node to the path till now
                    curPair.second.push_back(u);
                    // update the passed 'path' vector with the path so far.
                    path = curPair.second; // all nodes will be copied into path
                    return true;
                }
                
                // Not our node, visit the node if unvisited
                if(u->visited == 0){
                    u->visited = 1;
                    // Create a new path with this node added.
                    // Path so far can be obtained from the pair in queue
                    vector<Node*> newPath(curPair.second);
                    newPath.push_back(u);
                    // Add the node and the path to it into the queue.
                    q.push(make_pair(u, newPath));
                }
            }
        }
    }
    
    return false;
}


class Node{
    public:
    Node(int val) 
    { 
        value = val; 
        visited=0; 
    }
        
    int value;
    vector<Node*> adjNodes;
    int visited;
};