In BFS traversing we maintain a Queue to store nodes. Using the following loop we do bfs and push the nodes in the queue :
while(!Q.empty()) {
s = Q.front();
//cout << s << " ";
Q.pop_front();
// while exploring the nodes of s we only push the adjacent nodes of s
// explore adjacent loop
for(i : i = adjacent nodes of s) {
if(i is visited) {
mark i as visited;
// marking a node as visited does not mean fully explored
Q.push(i);
}
}
}
Queue makes it possible to push the nodes that are close to source earlier.
If we say that A is a node and it is at a distance d from the Source.While exploring (and pushing its adjacents in Queue) the adjacent nodes of A we touch a layer of nodes which are at distance of (d+1) from the source. (not more than that). And without completing (exploring) the layer of nodes at distance d from source we never explore a node which is at distance (d+1) from the source (how this even possible ? yes : because we are using queue not stack ) . This ensures that, whatever be the nodes in the queue in a particular time , the distance from source to any one of those nodes do not differ by more than 1.
conclusion:
distance[a] - distance[b] = 1,-1,0
// a and b are nodes in the queue in a particular time
// distance[a] = distance of a from source
Since a and b are in the queue, they are reachable from source S. There may or may not be direct path to go from a to b or b to a. We do not bother about that, because there is definitely a path via S : a--to--S--to--b.
ALL ARE CORRECT.