How to find the distance between two nodes using BFS?

Question

I wrote this BFS code in C ++ using the wikipedia pseudocode. The function takes two parameters s, t. Where s is the source of the node and t is the target, if the target is equal, the search returns the object itself, otherwise it returns -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 on Wikipedia:

Width and width search can be used to solve many problems of graph theory, for example:
Search for the shortest path between two nodes u and v (with the length of the path, measured by the number → edges)

How do I change my BFS function to return the shortest path from s to t and return -1 if the path does not exist?

Answer 1

When you create a new node, keep track of the identifier of the parent that generated the node. Then, when you reach the goal, you simply follow the parents back until you reach the state of beginning. You can, for example, mark the beginning as your own parent element, which means that this is the initial state. Or simply use the predefined value (-1) to say that there is no parent.

Thus, in your code, instead of marking the state, as shown, there is a parent identifier. Parent IDs can be set to -1 first, and then updated when they are changed. The parent ID can only have an arrangement in the parent graph structure.

Answer 2

The first width search, by definition, visits all nodes at a distance d from the starting point before visiting any nodes at a distance d+1 . Therefore, when you cross the graph in the first order, the first time you meet the node target, you get there along the shortest possible route.

Nathan S. 'The answer is correct, although I hope this answer gives more intuition about why this works. Paul Ding's commentary is also true; you can modify Nathan's answer to track the distance, and not the actual path is pretty trivial.