How to find the distance between two nodes using BFS?

Question

I wrote this code of BFS in c++ using wikipedia's pseudocode. The function takes two parameters s,t. Where s is the source node and t is the target, if the target is fount, the the search return the target itself, or else it return -1. Here is my code:

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

struct vertex{
vector<int> edges;
bool visited;
};

int dist = 0;

int BFS(vertex Graph[],int v,int target){
deque<int> Q;
Q.push_front(v);
Graph[v].visited = true;
    while(!Q.empty()){
        int t = Q.back();
        Q.pop_back();
            if(t == target){
                return t;
            }
            for(unsigned int i = 0;i < Graph[t].edges.size();i++){
                int u = Graph[t].edges[i];
                if(!Graph[u].visited){
                    Graph[u].visited = true;
                    Q.push_front(u);
                }
            }
    }
    return -1;
} 

int main(){
int n;
cin >> n;
vertex Graph[n];
int k;
cin >> k;
for(int i = 0;i < k; i++){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    Graph[a].edges.push_back(b);
    Graph[b].edges.push_back(a);
}

for(int i = 0;i < n; i++){
    Graph[i].visited = false;
}

int s,t;
cin >> s >> t;

cout << BFS(Graph,s,t);

  }

I read this in wikipedia :

Breadth-first search can be used to solve many problems in graph theory, for example:
Finding the shortest path between two nodes u and v (with path length measured by number > > of edges)

How do i change my function BFS to return the shortest path from s to t and return -1 if no path exists?

Solution 1

When you generate a new node, keep track of the id of the parent that generated the node. Then, when you reach the goal, you just trace the parents backwards until you reach the start state. You can, for instance, mark the start as its own parent, which means that it is the start state. Or, just use a pre-defined value (-1) to say there is no parent.

So, in your code, instead of marking a state as visited, have a parent id. Parent ids can be set to -1 initially, and then updated when they are changed. The parent id can just the location in the graph structure of the parent.

Solution 2

Breadth-first search, by definition, visits all nodes at distance d from the starting point before visiting any nodes at distance d+1. So when you traverse the graph in breadth-first order, the first time you encounter the target node, you've gotten there by the shortest possible route.

Nathan S.' answer is correct, though I hope this answer provides some more intuition about why this works. Paul Dinh's comment is also correct; you can modify Nathan's answer to track distance instead of the actual path pretty trivially.