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?

Answer 1

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.